求解斐波那契数列的方法.doc

《求解斐波那契数列的方法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、ExperiencingMagicAlgorithms实验室9#204实验目的或要求1.Designaninteractiveuserinterface(e.g.,amenu)foruser’sselection,ifpossible,agraphicaluserinterfaceisbest.2.UsingtheiterativealgorithmtofindthelargestnsuchthatthenthFibonaccinumberdosenotexceedthecomputer’smaximumintegervalue(e.g，232-1forint).

2、3.Accordingtothelargestncomputedinsubtask2,computethenthFibonaccinumberbytherecursivedefinition-basedalgorithm,canitfinishin5minute?4.Computethelargestnthatyourcomputercangiveasolutionin1,5,or10minutesbytherecursivedefinition-basedalgorithm,anddothesamethingbytheiterativealgorithm.5.C

3、omputethenthFibonaccinumberintheclosedformF(n)=[fn/sqrt(5)]inanefficientway.Whatisthesmallestnwhenanerroroccurs?6.ComputethenthFibonaccinumberbythematrix-multiplication-basedformulaattheendofChapter2.5.2oftextbook.7.Comparethenumberofbasicoperationsofthe4differentalgorithmsforthesamei

4、nputn,Trytograspthedramaticallydifferentgrowthrateoflogarithmic,linearandexponential.实验原理（算法流程）求解斐波那契数列的方法:1.递推算法根据递推公式可以很容易想到用递归的方法求解第n+1项的值，代码如下：longFibonacci_digui(inti){if(i==1

5、

6、i==0)returni;if(i>1)returnFibonacci_digui(i-1)+Fibonacci_digui(i-2);}这种方法在计算F[n]时，需要计算从F[2]到F[n-1]每一项的值

7、，这样简单的递归式存在着很多的重复计算，如求F[5]=F[4]+F[3]，在求F[4]的时候也需要求一次F[3]的大小，等等。2.迭代算法为了减少上述的重复运算，可以用一个数组存储所有已经计算过的项。这样便可以达到用空间换时间的目的。在这种情况下，时间复杂度为O(N)，而空间复杂度也为O(N)。longFibonacci(inti){inta=0,b=1,c=1;if(i==1

8、

9、i==0)returni;if(i>1){for(intj=2;j<=i;j++){c=a+b;a=b;b=c;};}}3.用公式法计算Fibonacci如果我们知道一个数列的通项公式，

10、利用公式来计算会更加容易。但公式引入了无理数，所以不能保证结果的精度。doubleFibonacci_formula(intn){doublea=1.0,b=1.0;for(inti=1;i<=n;i++){a*=(1+sqrt5)/2;实验原理（算法流程）b*=(1-sqrt5)/2;}}4.流程图ENDnoyes显示结果Fibonacci_a_minute();1分钟内能计算的FibonaccimaxN();计算机能表示的最大的FibonacciFn();求第N个Fibonacci数Fibonacci_digui();递归法计算第N个FibonacciFibo

11、nacci();用迭代法计算第N个Fibonacciif(Fibonacci_formula(i)!=Fibonacci(i))menu()；Fibonacci();Main()程序界面（效果图）程序界面（效果图）程序代码#include#includeusingnamespacestd;constdoublesqrt5=sqrt(5.0);longFibonacci(inti)//用迭代的方法计算第N个Fibonacci,返回第N个Fibonacci{inta=0,b=1,c=1;//a储存F（n-2）,b储存F（n-1），c储

12、存F（n）