Fibonacii数列，兔子问题-白红宇

Fibonacii数列，兔子问题

阅读量：5984 次

发布时间：2019-06-20

本文共 2789 字，大约阅读时间需要 9 分钟。

Fibonacci

数列

<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

Fibonacci

背景知识

斐波那契:

比萨德列奥纳多，又称斐波那契（

Leonardo Pisano ,Fibonacci, Leonardo Bigollo

，

1175

年

-1250

年），意大利数学家，西方第一个研究斐波那契数，并将现代书写数和乘数的位值表示法系统引入欧洲。

Fibonacci

引出

斐波那契

在《算盘书》中提出了一个有趣的兔子问题：一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？

我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔总数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；

类推表如下：

经过月数	0	1	2	3	4	5	6	7	8	9	10	11	12
幼仔对数	1	0	1	1	2	3	5	8	13	21	34	55	89
成兔对数	0	1	1	2	3	5	8	13	21	34	55	89	144
总体对数	1	1	2	3	5	8	13	21	34	55	89	144	233

从一年的总体对数中可以发现

从第二个月开始，其数量是前两个月的数量的和，所以得出递推公式为：

F(n)=F(n-1)+F(n-2)(n>=2) (1)

Fibonacci

数列的性质

1．

F(n)=F(n-1)+F(n-2)

其任意一项平方数为其前项和后项的积加一或者减一

F(n)*F(n)=F(n-1)*F(n+1)+/-1

任取相邻的四个斐波那契数，中间两数之积（内积）与两边两数之积（外积）相差

Fibonacci

数列的程序实现

1. 递归实现

static int Fib1(int n)
                {
                        int []result = new int[]{ 0, 1 };
                        if(n<2) return result[n];
                        return Fib1(n-1)+Fib1(n-2);
                }

2．非递归实现(迭代法)

static int Fib2(int n)
                {
                        int[] result = new int[] { 0, 1 };
                        if (n < 2) return result[n];
                        int n1=0,n2=1,retTemp=0;
                        for (int i = 2; i <=n; i++)
                        {
                                retTemp = n1 + n2;
                                n1 = n2;
                                n2 = retTemp;
                        }
                        return retTemp;
                }

2．创新法(矩阵公式)

存在一个Fibonacii的矩阵恒等式，其形式如下所示：