Fibonacci 定义

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。具体是这样一个数列：1、1、2、3、5、8、13、21、34、……可以定义为以下关系：

当n>1时，这个数列第n项的值是前两项之和

实现 Fibonacci 代码

由 Fibonacci 定义可得数列可递归地计算如下：

int fibonacci (int n) {if (n <= 1) return 1;return fibonacci(n - 1) + fibonacci(n - 2);}

之前 “函数的递归与迭代” 中提到用递归方法实现斐波那契数列效率十分低，见链接：/qq_44759710/article/details/99686359.

为此我们可以使用迭代法，用循环实现：

int fib(int n) {int result;int result1;int result2;result = result1 = 1;while (n > 2){n--;result2 = result1;result1 = result;result = result1 + result2;}return result;}

求 Fibonacci 通项公式

由定义可推导出通项公式：

方法1：待定系数法构造等比数列（初等代数解法）

设常数 r , s ,使得

F( n ) - r * F(n - 1) = s * [F(n - 1) - r * F(n - 2)]

则有 r + s = 1，- r * s = 1

当 n >= 3时，有

联立以上 n - 2 个式子可得：

可化简且进一步转换为：

（显然这是一个以 s^(n - 1) 为首项，以r^(n - 1)为末项，r / s 为公比的等比数列的各项的和）

则

方法2：待定系数法构造等比数列（初等代数解法）

方法3：母函数法

此处只详细解释方法一

Fibonacci 的运用

从上述通项公式，我们可以找到很熟悉的数字

r = - ([5 ^ (1 / 2) - 1] / 2 近似等于0.618

找出几个数据，求出前一项与后一项的比值：

1÷1=1

1÷2=0.5

2÷3=0.666

3÷5=0.6

5÷8=0.625

……

144÷233=0.618025

……

46368÷75025=0.6180339886

……

容易得出比值越来越接近0.618，即黄金比

这个关系可容易证得：

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

两边同时除以 F(n + 1)，可得：

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

设lim [F(n) / F(n + 1)] = lim [F(n + 1) / F(n + 2)] = x

即有 x + 1 = 1 / x

易得 x = [5 ^ (1 / 2) - 1] / 2 = 0.618

斐波那契数亦是经常出现在我们的生活中：

例一：

如图，将数列关系转为正方形边长问题，可得出以上具有美感的图片和海螺的纹路类似，自然界中常见的松果、向日葵等的花瓣、果实排列都可以找到类似的规律

例二：

求矩形面积：

如图，矩形的长宽变化为斐波那契数列，可以得：

正方形面积之和可以转换成求矩形的面积

例三：关于斐波那契数列对于数的整除

每2个连续的数中有且只有一个被2整除，

每3个连续的数中有且只有一个被3整除，

每4个连续的数中有且只有一个被5整除，

每5个连续的数中有且只有一个被8整除，

……

每n个连续的数中有且只有一个被F(n)整除

例四：兔子问题

被称为兔子数列的斐波那契数列，解决的是一个关于兔子繁殖的问题：

“……兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死，那么一年以后可以繁殖多少对兔子？”

经过对题目的分析，可以得到兔子的繁殖情况：

由上表可以得出以下代码来求得兔子在一段时间后的对数：

int rabbit(int month) {int num;int num1;int num2;num = num1 = 1;while (month > 2){month--;num2 = num1;num1 = num;num = num1 + num2;}return num;}