欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

经典的兔子生兔子问题(C#递归解法)

程序员文章站 2022-06-22 17:33:55
古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 思路:先求出每个月新增的兔子,再用循环求和即可算出这个月总的兔子数。 月份 新增加兔子 1 1 2 0 3 1 4 1 5 1 + 1 6 1 + 1 + ......

古典问题:有一对兔子,从出生后第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...

结论:

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