斐波那契数列各种语言的解法.docx

斐波那契数列百科名片“斐波那契数列”是意大利数学家列昂纳多斐波那契首先研究的一种递归数列， 它的每一项都等于前两项之和。 此数列的前几项为1，1，2，3，5等等。 在生物数学中，许多生物现象都会呈现出斐波那契数列的规律。斐波那契数列相邻两项的比值趋近于黄金分割数。此外，斐波那契数也以密码的方式出现在诸如达芬奇密码的影视书籍中。目录隐藏【奇妙的属性】【影视链接】【相关的数学问题】【斐波那契数列别名】斐波那契数列公式的推导【C语言程序】【C#语言程序】【Java语言程序】【JavaScript语言程序】【Pascal语言程序】【PL/SQL程序】【数列与矩阵】【数列值的另一种求法】【数列的前若干项】【斐波那契数列的应用】 【奇妙的属性】【影视链接】【相关的数学问题】【斐波那契数列别名】斐波那契数列公式的推导【C语言程序】【C#语言程序】【Java语言程序】【JavaScript语言程序】【Pascal语言程序】【PL/SQL程序】【数列与矩阵】【数列值的另一种求法】【数列的前若干项】【斐波那契数列的应用】“斐波那契数列(Fibonacci)”的发明者，是意大利数学家列昂纳多斐波那契（Leonardo Fibonacci，生于公元1170年，卒于1240年，籍贯大概是比萨）。他被人称作“比萨的列昂纳多”。1202年，他撰写了珠算原理 (Liber Abaci)一书。他是第一个研究了印度和阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事，派驻地点相当于今日的阿尔及利亚地区， 列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及、叙利亚、希腊、西西里和普罗旺斯研究数学。斐波那契数列通项公式斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、这个数列从第三项开始，每一项都等于前两项之和。它的通项公式为:(见图)（又叫“比内公式”，是用无理数表示有理数的一个范例。）有趣的是：这样一个完全是自然数的数列，通项公式居然是用无理数来表达的。编辑本段【奇妙的属性】随着数列项数的增加，前一项与后一项之比越来越逼近黄金分割的数值0.6180339887从第二项开始，每个奇数项的平方都比前后两项之积多1，每个偶数项的平方都比前后两项之积少1。（注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如第五项的平方比前后两项之积多1，第四项的平方比前后两项之积少1）如果你看到有这样一个题目：某人把一个8*8的方格切成四块，拼成一个5*13的长方形，故作惊讶地问你：为什么6465？其实就是利用了斐波那契 数列的这个性质：5、8、13正是数列中相邻的三项，事实上前后两块的面积确实差1，只不过后面那个图中有一条细长的狭缝，一般人不容易注意到。斐波那契数列的第n项同时也代表了集合1,2,.,n中所有不包含相邻正整数的子集个数。斐波那契数列（f(n)，f(0)=0，f(1)=1，f(2)=1，f(3)=2）的其他性质：1.f(0)+f(1)+f(2)+f(n)=f(n+2)-12.f(1)+f(3)+f(5)+f(2n-1)=f(2n)3.f(2)+f(4)+f(6)+f(2n) =f(2n+1)-14.f(0)2+f(1)2+f(n)2=f(n)f(n+1)5.f(0)-f(1)+f(2)-+(-1)nf(n)=(-1)nf(n+1)-f(n)+16.f(m+n)=f(m-1)f(n-1)+f(m)f(n)利用这一点，可以用程序编出时间复杂度仅为O（log n）的程序。7.f(n)2=(-1)(n-1)+f(n-1)f(n+1)8.f(2n-1)=f(n)2-f(n-2)29.3f(n)=f(n+2)+f(n-2)10.f(2n-2m-2)f(2n)+f(2n+2)=f(2m+2)+f(4n-2m) nm-1,且n1斐波那契数列在杨辉三角中隐藏着斐波那契数列11 11 2 11 3 3 11 4 6 4 1过第一行的“1”向左下方做45度斜线，之后做直线的平行线，将每条直线所过的数加起来，即得一数列1、1、2、3、5、8、斐波那契数与植物花瓣3百合和蝴蝶花5蓝花耧斗菜、金凤花、飞燕草8翠雀花13金盏21紫宛34、55、89雏菊斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如，在树木的枝干上选一片叶子，记其为数0，然后依序点数叶子（假定没有折损），直到到达与那息 叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个 循回中叶子数与叶子旋转圈数的比称为叶序（源自希腊词，意即叶子的排列）比。多数的叶序比呈现为斐波那契数的比。斐波那契数列与黄金比1/1=1，2/1=2，3/2=1.5，5/3=1.6，8/5=1.6，89/55=1.61818，233/144=1.618055编辑本段【影视链接】斐波那契数列在欧美可谓是尽人皆知，于是在电影这种通俗艺术中也时常出现，比如在风靡一时的达芬奇密码里它就作为一个重要的符号和情节线索出现， 在魔法玩具城里又是在店主招聘会计时随口问的问题。可见此数列就像黄金分割一样流行。可是虽说叫得上名，多数人也就背过前几个数，并没有深入理解研 究。编辑本段【相关的数学问题】1.排列组合有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?这就是一个斐波那契数列：登上第一级台阶有一种登法；登上两级台阶，有两种登法；登上三级台阶，有三种登法；登上四级台阶，有五种登法1，2，3，5，8，13所以，登上十级，有89种走法。2.数列中相邻两项的前项比后项的极限当n趋于无穷大时，F(n)/F(n+1)的极限是多少？这个可由它的通项公式直接得到，极限是(-1+5)/2，这个就是黄金分割的数值，也是代表大自然的和谐的一个数字。3.求递推数列a(1)=1，a(n+1)=1+1/a(n)的通项公式由数学归纳法可以得到：a(n)=F(n+1)/F(n)，将斐波那契数列的通项式代入，化简就得结果。编辑本段【斐波那契数列别名】斐波那契数列又因数学家列昂纳多斐波那契以兔子繁殖为例子而引入，故又称为“兔子数列”。一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔都不死，那么一年以后可以繁殖多少对兔子？我们不妨拿新出生的一对小兔子分析一下：第一个月小兔子没有繁殖能力，所以还是一对；两个月后，生下一对小兔民数共有两对；三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；依次类推可以列出下表：经过月数：-1-2-3-4-5-6-7-8-9-10-11-12兔子对数：-1-1-2-3-5-8-13-21-34-55-89-144表中数字1，1，2，3，5，8构成了一个数列。这个数列有关十分明显的特点，那是：前面相邻两项之和，构成了后一项。这个特点的证明：每月的大兔子数为上月的兔子数，每月的小兔子数为上月的大兔子数，即上上月的兔子数，相加。这个数列是意大利中世纪数学家斐波那契在算盘全书中提出的，这个级数的通项公式，除了具有a(n+2)=an+a(n+1)的性质外，还可以证明通项公式为：an=（1/5）*(1+5/2)n-(1-5/2)n（n=1,2,3.）编辑本段斐波那契数列公式的推导【斐波那契数列通项公式的推导】斐波那契数列：1、1、2、3、5、8、13、21、如果设F(n)为该数列的第n项(nN+)。那么这句话可以写成如下形式：F(0) = 0，F(1)=F(2)=1，F(n)=F(n-1)+F(n-2) (n3)显然这是一个线性递推数列。通项公式的推导方法一：利用特征方程线性递推数列的特征方程为：X2=X+1解得X1=(1+5)/2,，X2=(1-5)/2则F(n)=C1*X1n + C2*X2nF(1)=F(2)=1C1*X1 + C2*X2C1*X12 + C2*X22解得C1=1/5，C2=-1/5F(n)=(1/5)*(1+5)/2n - (1-5)/2n（5表示根号5）通项公式的推导方法二：普通方法设常数r，s使得F(n)-r*F(n-1)=s*F(n-1)-r*F(n-2)则r+s=1， -rs=1n3时，有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) + r2*F(n-2)= s(n-1) + r*s(n-2) + r2*s(n-3) + r3*F(n-3)= s(n-1) + r*s(n-2) + r2*s(n-3) + r(n-2)*s + r(n-1)*F(1)= s(n-1) + r*s(n-2) + r2*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)=(sn - rn)/(s-r)r+s=1， -rs=1的一解为 s=(1+5)/2，r=(1-5)/2则F(n)=(1/5)*(1+5)/2n - (1-5)/2n迭代法已知a1=1,a2=1,an=a(n-1)+a(n-2)(n=3),求数列an的通项公式解 :设an-a(n-1)=(a(n-1)-a(n-2)得+=1=-1构造方程x²-x-1=0,解得=(1-5)/2,=(1+5)/2或=(1+5)/2,=(1-5)/2所以an-(1-5)/2*a(n-1)=(1+5)/2*(a(n-1)-(1-5)/2*a(n-2)=(1+5)/2(n-2)*(a2-(1-5)/2*a1)1an-(1+5)/2*a(n-1)=(1-5)/2*(a(n-1)-(1+5)/2*a(n-2)=(1-5)/2(n-2)*(a2-(1+5)/2*a1)2由式1,式2,可得an=(1+5)/2(n-2)*(a2-(1-5)/2*a1)3an=(1-5)/2(n-2)*(a2-(1+5)/2*a1)4将式3*(1+5)/2-式4*(1-5)/2,化简得an=(1/5)*(1+5)/2n - (1-5)/2n编辑本段【C语言程序】/利用循环输出前40项#include int main()long fib41 = 0,1;int i;for(i=2;i41;i+)fibi = fibi-1+fibi-2;for(i=1;i41;i+)printf(F%d=%dn,i,fibi);getch();return 0;/利用递归实现指定项输出第n项和。（1n25)#includevoid main()long int f1,f2;int n,i,c;scanf(%d,&n);f1=1;f2=1;for(i=1;i=n;i+)c=i+1;printf(%dItem=%ld %dItem=%ld ,i,f1,c,f2);if(i%2=0)printf(n);f1=f1+f2;f2=f2+f1;编辑本段【C#语言程序】public class Fibonacci/NormRenstatic void Main(string args)int x = 0, y = 1;for (int j = 1; j 10; j+, y = x + y, x = y - x)Console.Write(y + );编辑本段【Java语言程序】public class Fibonaccipublic static void main(String args)int x=1,y=1;System.out.println(x+ );for(int i=1;i=20;i+)System.out.println(y+ );y=x+y;x=y-x;编辑本段【JavaScript语言程序】function Fibonacci(num)if(num 0 thenbegininc(c0);inc(cc0+1,cc0 div 10);cc0:=cc0 mod 10;end;a:=b; b:=c;end;beginassign(input,d:input.txt);assign(output,d:output.txt);reset(input);rewrite(output);while not eof dobeginreadln(n);fillchar(a,sizeof(a),0);fillchar(b,sizeof(b),0);a0:=1; a1:=1;b0:=1; b1:=1;if n=1 then write(1)elseif n=2 then write(1)elsebeginfor k:=3 to n doadd(a,b,c);for k:=c0 downto 1 dowrite(ck);end;writeln;end;close(input);close(output);end.以上程序为 FZU 1060 的标程.编辑本段【PL/SQL程序】declare i number :=0;j number :=1;x number :=1;beginwhile x2），每段的长度不小于1cm，如果其中任意三小段都不能拼成三角形，则n的最大值为多少？分析：由于形成三角形的充要条件是任何两边之和大于第三边，因此不构成三角形的条件就是任意两边之和不超过最大边。截成的铁丝最小为1，因此可以放2 个1，第三条线段就是2（为了使得n最大，因此要使剩下来的铁丝尽可能长，因此每一条线段总是前面的相邻2段之和），依次为：1、1、2、3、5、8、 13、21、34、55，以上各数之和为143，与144相差1，因此可以取最后一段为56，这时n达到最大为10。我们看到，“每段的长度不小于1”这个条件起了控制全局的作用，正是这个最小数1产生了斐波那契数列，如果把1换成其他数，递推关系保留了，但这个数列消失了。这里，三角形的三边关系定理和斐波那契数列发生了一个联系。在这个问题中，144143，这个143是斐波那契数列的前n项和，我们是把144超出143的部分加到最后的一个数上去，如果加到其他数上，就有3条线段可以构成三角形了。记忆是一种可以被用来避免重复昂贵的运算以加速程序的技术，先展示一个队斐波那契数列（Fibonacci Sequence）的实现，它用两个递归调用来计算给定输入的值。function fibonacci(x) if (x 2) return 1;return fibonacci(x - 1) + fibonacci(x - 2);斐波那契数列的计算是十分昂贵的，它迅速产生了太多的递归调用给浏览器来处理。同归把函数包裹在一个闭包中，我们可以手工技艺计算过的值以优化这个方法。var fibonacci