求解斐波那契数列的方法

ExperiencingMagicAlgorithms实验室9#204实验目的或要求1.Designaninteractiveuserinterface(e.g.,amenu)foruser’sselection,ifpossible,agraphicaluserinterfaceisbest.2.UsingtheiterativealgorithmtofindthelargestnsuchthatthenthFibonaccinumberdosenotexceedthecomputer’smaximumintegervalue(e.g，232-1forint).3.Accordingtothelargestncomputedinsubtask2,computethenthFibonaccinumberbytherecursivedefinition-basedalgorithm,canitfinishin5minute?4.Computethelargestnthatyourcomputercangiveasolutionin1,5,or10minutesbytherecursivedefinition-basedalgorithm,anddothesamethingbytheiterativealgorithm.5.ComputethenthFibonaccinumberintheclosedformF(n)=[n/sqrt(5)]inanefficientway.Whatisthesmallestnwhenanerroroccurs?6.ComputethenthFibonaccinumberbythematrix-multiplication-basedformulaattheendofChapter2.5.2oftextbook.7.Comparethenumberofbasicoperationsofthe4differentalgorithmsforthesameinputn,Trytograspthedramaticallydifferentgrowthrateoflogarithmic,linearandexponential.实验原理（算法流程）求解斐波那契数列的方法:1.递推算法根据递推公式可以很容易想到用递归的方法求解第n+1项的值，代码如下：longFibonacci_digui(inti){if(i==1||i==0)returni;if(i1)returnFibonacci_digui(i-1)+Fibonacci_digui(i-2);}这种方法在计算F[n]时，需要计算从F[2]到F[n-1]每一项的值，这样简单的递归式存在着很多的重复计算，如求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||i==0)returni;if(i1){for(intj=2;j=i;j++){c=a+b;a=b;b=c;};}}3.用公式法计算Fibonacci如果我们知道一个数列的通项公式，利用公式来计算会更加容易。但公式引入了无理数，所以不能保证结果的精度。doubleFibonacci_formula(intn){doublea=1.0,b=1.0;for(inti=1;i=n;i++){a*=(1+sqrt5)/2;实验原理（算法流程）b*=(1-sqrt5)/2;}}4.流程图Main()menu()；Fibonacci();用迭代法计算第N个FibonacciFibonacci_digui();递归法计算第N个FibonacciFibonacci_a_minute();1分钟内能计算的FibonaccimaxN();计算机能表示的最大的FibonacciFn();求第N个Fibonacci数Fibonacci();if(Fibonacci_formula(i)!=Fibonacci(i))END显示结果yesno程序界面（效果图）程序界面（效果图）程序代码#includecmath#includeiostreamusingnamespacestd;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储存F（n）。所以c=a+b;if(i==1||i==0)returni;if(i1){for(intj=2;j=i;j++){c=a+b;a=b;b=c;//coutc'';};}returnc;}longFibonacci_digui(inti)//用递归的方法计算第N个Fibonacci，返回第N个Fibonacci{if(i==1||i==0)returni;if(i1)returnFibonacci_digui(i-1)+Fibonacci_digui(i-2);}intmaxN()/返回计算机能表示的最大的Fibonacci时N的值，{intn;for(n=1;Fibonacci(n)=1134903170;n++);returnn;}voidFn()//读入N，然后输出第N个Fibonacci程序代码{inta;coutEnteranumber:;cina;couttheathFibonacciis:Fibonacci(a)endlendl;}voidFibonacci_a_minute()//测试规定时间内用递归算法能计算出的最大Fibonacci，如1分钟内最多能计算几个{for(intb=1;b50;b++){coutbendl;coutFibonacci_digui(b)endl;//递归的输出};}doubleFibonacci_formula(intn)//用公式法计算Fibonacci{doublea=1.0,b=1.0;for(inti=1;i=n;i++){a*=(1+sqrt5)/2;b*=(1-sqrt5)/2;}return(a-b)/sqrt5;}intmenu(){cout***********************************************************endl;cout==1---求第N个Fibonacci数==endl;cout==2---计算机能算出最大Fibonacci时N的值==endl;cout==3---计算1分钟内能计算几个Fibonacci==endl;cout==4---用公式法计算Fibonacci，当出现错误时，N为多少==endl;cout==5---退出程序==endl;cout***********************************************************endl;intselect;inta;cout请选择菜单:;程序代码cinselect;if(select==1){Fn();menu();};if(select==2){coutthelargestnsuchthatthenthFibonaccinumberdosenotexceedthecomputer’smaximumintegervalueis:maxN()endlendl;menu();};if(select==3){Fibonacci_a_minute();//一分钟41，两分钟42次，在我的电脑上menu();};if(select==4){//coutFibonacci_formula(3)endl;for(inti=1;i=50;i++)if(Fibonacci_formula(i)!=Fibonacci(i)){cout第i个数开始用公式法算出来的Fibonacci有错误endlendl;break;}menu();}if(select==5){return0;};return0;}intmain(){menu();return0;}//coutmaxN();//输入任何数结束程序实验结果分析及心得体会本次实验探讨了Fibonacci数的内容，对于如何计算Fibonacci数以及各种计算Fibonacci数算的方法有了深刻的了解；（如递归算法对于有较大的数据输入时，运行时间最慢；迭代的优点在于记录每次运算的结果，而不必重复计算以前的数据）同时也感叹算法的神奇，如何是计算过程更为完美时间更短其关键就在于设计的算法在实验的过程中，遇到不少阻力。因而以后要多花力气学习C++编程语言，必须要加强这方面的训练，这样才能在将编程思想和算法转换为代码的时候能得心应手。这次课设做还有许多没有考虑周到的地方，希望老师指出。组员分工求第N个Fibonacci数---XX计算机能算出最大Fibonacci时N的值---XX计算1分钟内能计算几个Fibonacci---XX用公式法计算Fibonacci，当出现错误时，N为多少---XX成绩评定教师签名：2010年11月日