·【斐波那契数列别名】
·【斐波那挈数列通项公式的推导】
·【c语言程序】
·【pascal语言程序】
·【数列与矩阵】
·【数列值的另一种求法】
·【数列的前若干项】
“斐波那契数列”的发明者，是意大利数学家列昂纳多·斐波那契（leonardofibonacci，生于公元1170年，卒于1240年。籍贯大概是比萨）。他被人称作“比萨的列昂纳多”。1202年，他撰写了《珠算原理》(liberabaci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区，列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21……
这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为：(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}【√5表示根号5】
很有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。
【该数列有很多奇妙的属性】
比如：随着数列项数的增加，前一项与后一项之比越逼近黄金分割0.6180339887……
还有一项性质，从第二项开始，每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1。
如果你看到有这样一个题目：某人把一个8*8的方格切成四块，拼成一个5*13的长方形，故作惊讶地问你：为什么64＝65？其实就是利用了斐波那契数列的这个性质：5、8、13正是数列中相邻的三项，事实上前后两块的面积确实差1，只不过后面那个图中有一条细长的狭缝，一般人不容易注意到。
如果任意挑两个数为起始，比如5、-2.4，然后两项两项地相加下去，形成5、-2.4、2.6、0.2、2.8、3、5.8、8.8、14.6……等，你将发现随着数列的发展，前后两项之比也越来越逼近黄金分割，且某一项的平方与前后两项之积的差值也交替相差某个值。
斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数。
【斐波那契数列别名】
斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。
斐波那契数列
一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？
我们不妨拿新出生的一对小兔子分析一下：
第一个月小兔子没有繁殖能力，所以还是一对;
两个月后，生下一对小兔民数共有两对;
三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对;
－－－－－－
依次类推可以列出下表：
经过月数：0123456789101112
兔子对数：1123581321345589144233
表中数字1，1，2，3，5，8－－－构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。
这个数列是意大利中世纪数学家斐波那契在＜算盘全书＞中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)/的性质外，还可以证明通项公式为：an=1/√[（1＋√5/2)n-(1-√5/2)n](n=1,2,3.....）
【斐波那挈数列通项公式的推导】
斐波那契数列：1，1，2，3，5，8，13，21……
如果设f(n)为该数列的第n项(n∈n+)。那么这句话可以写成如下形式：
f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)(n≥3)
显然这是一个线性递推数列。
通项公式的推导方法一：利用特征方程
线性递推数列的特征方程为：
x^2=x+1
解得
x1=(1+√5)/2,x2=(1-√5)/2.
则f(n)=c1*x1^n+c2*x2^n
∵f(1)=f(2)=1
∴c1*x1+c2*x2
c1*x1^2+c2*x2^2
解得c1=1/√5，c2=-1/√5
∴f(n)=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}【√5表示根号5】
通项公式的推导方法二：普通方法
设常数r,s
使得f(n)-r*f(n-1)=s*[f(n-1)-r*f(n-2)]
则r+s=1,-rs=1
n≥3时，有
f(n)-r*f(n-1)=s*[f(n-1)-r*f(n-2)]
f(n-1)-r*f(n-2)=s*[f(n-2)-r*f(n-3)]
f(n-2)-r*f(n-3)=s*[f(n-3)-r*f(n-4)]
……
f(3)-r*f(2)=s*[f(2)-r*f(1)]
将以上n-2个式子相乘，得：
f(n)-r*f(n-1)=[s^(n-2)]*[f(2)-r*f(1)]
∵s=1-r，f(1)=f(2)=1
上式可化简得：
f(n)=s^(n-1)+r*f(n-1)
那么：
f(n)=s^(n-1)+r*f(n-1)
=s^(n-1)+r*s^(n-2)+r^2*f(n-2)
=s^(n-1)+r*s^(n-2)+r^2*s^(n-3)+r^3*f(n-3)
……
=s^(n-1)+r*s^(n-2)+r^2*s^(n-3)+……+r^(n-2)*s+r^(n-1)*f(1)
=s^(n-1)+r*s^(n-2)+r^2*s^(n-3)+……+r^(n-2)*s+r^(n-1)
（这是一个以s^(n-1)为首项、以r^(n-1)为末项、r/s为公差的等比数列的各项的和）
=[s^(n-1)-r^(n-1)*r/s]/(1-r/s)
=(s^n-r^n)/(s-r)
r+s=1,-rs=1的一解为s=(1+√5)/2,r=(1-√5)/2
则f(n)=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}
【c语言程序】
main()
{
longfib[40]={1,1};
inti;
for(i=2;i<40;i++)
{
fib[i]=fib[i-1]+fib[i-2];
}
for(i=0;i<40;i++)
{
printf("f%d==%d\n",i,fib);
}
return0;
}
【pascal语言程序】var
fib:array[0..40]oflongint;
i:integer;
begin
fib[0]:=1;
fib[1]:=1;
fori:=2to39do
fib[i]:=fib[i-1]+fib[i-2];
fori:=0to39do
write('f',i,'=',fib[i]);
end.
【数列与矩阵】
对于斐波那契数列1,1,2,3,5,8,13…….有如下定义
f(n)=f(n-1)+f(n-2)
f(1)=1
f(2)=1
对于以下矩阵乘法
f(n+1)=11*f(n)
f(n)10f(n-1)
它的运算就是
f(n+1)=f(n)+f(n-1)
f(n)=f(n)
可见该矩阵的乘法完全符合斐波那契数列的定义
设1为b，11为c
110
可以用迭代得到:
斐波那契数列的某一项f(n)=(bc^(n-2))1
这就是斐波那契数列的矩阵乘法定义.
另矩阵乘法的一个运算法则a¬^n(n为偶数)=a^(n/2)*a^(n/2).
因此可以用递归的方法求得答案.
时间效率：o(logn)，比模拟法o(n)远远高效。
代码（pascal）
{变量matrix是二阶方阵,matrix是矩阵的英文}
programfibonacci;
type
matrix=array[1..2,1..2]ofqword;
var
c,cc:matrix;
n:integer;
functionmultiply(x,y:matrix):matrix;
var
temp:matrix;
begin
temp[1,1]:=x[1,1]*y[1,1]+x[1,2]*y[2,1];
temp[1,2]:=x[1,1]*y[1,2]+x[1,2]*y[2,2];
temp[2,1]:=x[2,1]*y[1,1]+x[2,2]*y[2,1];
temp[2,2]:=x[2,1]*y[1,2]+x[2,2]*y[2,2];
exit(temp);
end;
functiongetcc(n:integer):matrix;
var
temp:matrix;
t:integer;
begin
ifn=1thenexit(c);
t:=ndiv2;
temp:=getcc(t);
temp:=multiply(temp,temp);
ifodd(n)thenexit(multiply(temp,c))
elseexit(temp);
end;
procedureinit;
begin
readln(n);
c[1,1]:=1;
c[1,2]:=1;
c[2,1]:=1;
c[2,2]:=0;
ifn=1then
begin
writeln(1);
halt;
end;
ifn=2then
begin
writeln(1);
halt;
end;
cc:=getcc(n-2);
end;
procedurework;
begin
writeln(cc[1,1]+cc[1,2]);
end;
begin
init;
work;
end.
【数列值的另一种求法】
f(n)=[((sqrt(5)+1)/2)^n]
其中[x]表示取距离x最近的整数。
【数列的前若干项】11
21
32
43
55
68
713
821
934
1055
1189
12144
13233
14377
15610
16987
171597
182584
194181
206765
2110946
2217711
2328657
2446368
2575025
26121393
27196418
28317811
29514229
30832040
311346269
322178309
333524578
345702887
359227465
3614930352
3724157817
3839088169
3963245986
40102334155
41165580141
42267914296
43433494437
44701408733
451134903170
461836311903
472971215073
484807526976
497778742049
5012586269025
5120365011074
5232951280099
5353316291173
5486267571272
55139583862445
56225851433717
57365435296162
58591286729879
59956722026041
601548008755920
612504730781961
624052739537881
636557470319842
6410610209857723
6517167680177565
6627777890035288
6744945570212853
6872723460248141
69117669030460994
70190392490709135
71308061521170129
72498454011879264
73806515533049393
741304969544928657
752111485077978050
763416454622906707
775527939700884757
788944394323791464
7914472334024676221
8023416728348467685
8137889062373143906
8261305790721611591
8399194853094755497
84160500643816367088
85259695496911122585
86420196140727489673
87679891637638612258
881100087778366101931
891779979416004714189
902880067194370816120
914660046610375530309
927540113804746346429
......