VB.net 2010 视频教程 VB.net 2010 视频教程 python基础视频教程
SQL Server 2008 视频教程 c#入门经典教程 Visual Basic从门到精通视频教程
当前位置:
首页 > Python基础教程 >
  • C#教程之经典的兔子生兔子问题(C#递归解法)

古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

思路:先求出每个月新增的兔子,再用循环求和即可算出这个月总的兔子数。

月份  新增加兔子

1    1

2    0

3    1

4    1

5    1 + 1

6    1 + 1 + 1

7    (1 + 1 + 1)6月份新增的兔子 + (1 + 1)5月份新增的兔子

...    ...

n    n - 1月份新增的兔子 + n - 2月份新增的兔子

解法核心:每个月的新增的兔子都在下下个月以及以后的每个月生下一对新兔子,这对新兔子在下下个月以及以后的每个月都会生下一对新兔子,以此规律循环。

    因此,只要上个月有新增的兔子后,这个月都会新增和上个月新兔子数量同样的兔子,同时还会新增上上个月兔子数量的新兔子。这两个数量相加就得到这个月一共新增加的兔子。

用递归的方法求出每个月新增的兔子(自定义函数):

        static int NewRabbitOfMonth(int n)
        {
            if(n == 1)
            {
                return 1;
            }
            else if(n == 2)
            {
                return 0;
            }
            else
            {
                return NewRabbitOfMonth(n - 1) + NewRabbitOfMonth(n - 2); 
            }
        }

用循环求和的方法求出每个月的兔子总数(主函数):

        static void Main(string[] args)
        {
            Console.Write("请输入第几个月:");
            int n = int.Parse(Console.ReadLine());
            int sumRabbitOfMonth = 0;
            for(int i =1; i <= n; i++)
            {
                sumRabbitOfMonth += NewRabbitOfMonth(i);
            }
            Console.Write("第" + n + "个月共有" + sumRabbitOfMonth + "对兔子");
            Console.ReadLine();
        }
 

思考:

每个月新增的兔子数量实际上是一个斐波拉契数列:
1,0,1,1,2,3,5...

每个月总的兔子数量也是一个斐波拉契数列:

1,1,2,3,5,8,13...

下面个数列每一项减去上面个数量每一项得到的新数列也是斐波拉契数列:

0,1,1,2,3,5,8...

结论:

一个斐波拉契数量的每一项减去另一个斐波拉契数列的对应每一项得到的新数列也是斐波拉契数列。(待验证)

 


相关教程