斐波那契数列
一．论文 Fibonacci Sequence and Golden Section Number
2008年，某中学某班lzq牛在学校组织的“研究性学习”中，果断拒绝选任何本班教师的研究题目，而是“违反规定”地选择了其他老师的课题且单打独斗独立课题研究，发表重要论文《斐波那契数列和黄金分割率》。
论文有著名的兔子生殖问题引入，介绍了斐波那契数列。
1202 年，一本名为《珠算原理》（LiberAbaci）的书中提出了一个兔子繁殖的例子：
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？
设数列 F(n) 表示每个月兔子的数量，根据题意：
F(n)=F(n-1)+F(n-2)
F(1)=1
F(2)=2
试算得：
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
|
1
|
2
|
3
|
5
|
8
|
13
|
21
|
34
|
55
|
89
|
144
|
233
|
然而，伟大的数学家给我们的不仅仅是这个惊喜！如果再仔细地观察下去，计算相邻两
项的比例我们得到另外一张表：
|
n
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
|
F(n)
|
1
|
2
|
3
|
5
|
8
|
13
|
21
|
34
|
55
|
89
|
144
|
|
Ratio
|
0.5
|
0.666667
|
0.6
|
0.625
|
0.615385
|
0.619048
|
0.617647
|
0.618182
|
0.617978
|
0.618056
|
0.618026
|
即越来越接近黄金分割φ。
文章后面解出了斐波那契数列的通项公式，并证明当n趋向∞时比率等于黄金分割φ。后面还就黄金分割的若干应用做了介绍，包括三分求根和Nim取石。
最后，要强调，要感谢“第三中学八年级十二班”_gXX同学，“第三中学八年级十一班”lzq同学为本文做了大量工作。
二．关于斐波那契数列的求法
显然用计算机求的话，最简单的是写一个函数：
int Fibonacci(int i){
int ans;
if (i<3){
return i
};
Ans=fibonacci(i-1)+Fibonacci(i-2);
return ans;
}
然后显然递归求解。
易得复杂度与斐波那契数列的定义相同是黄金分割φ的n次方，即这是个指数算法。
考虑“备忘录”法的递推。
Int main(){
Int I,j;
Int f[100];
F[1]=1;
F[2]=2;
For (i=3;a<100;i++)
F[i]=f[i-1]+f[i-2];
Return 0;
}
复杂度为O(n)（不考虑高精度）。
这个对于所求项数比较大时并不实用，于是我们改用矩阵法。
令矩阵
A(n)=
|
F(n)
|
F(n-1)
|
|
F(n-1)
|
F(n-2)
|
令一个矩阵G满足：
A(n)=A(n-1)G
求得：
G=
易得G符合上式。
则：
A(n+c)=A(n)Gc
用一个快速幂矩阵乘法可以快速得出答案。
类似方法可以推广到F(n)=sum(ki*f(n-i))的矩阵求法。
| 
