C#实现斐波那契数列的几种方法整理
什么是斐波那契数列?经典数学问题之一;斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、……想必看到这个数列大家很容易的就推算出来后面好几项的值,那么到底有什么规律,简单说,就是前两项的和是第三项的值,用递归算法计第50位多少。
这个数列从第3项开始,每一项都等于前两项之和。
斐波那契数列:{1,1,2,3,5,8,13,21...}
递归算法,耗时最长的算法,效率很低。
publicstaticlongCalcA(intn) { if(n<=0)return0; if(n<=2)return1; returnchecked(CalcA(n-2)+CalcA(n-1)); }
通过循环来实现
publicstaticlongCalcB(intn) { if(n<=0)return0; vara=1L; varb=1L; varresult=1L; for(vari=3;i<=n;i++) { result=checked(a+b); a=b; b=result; } returnresult; }
通过循环的改进写法
publicstaticlongCalcC(intn) { if(n<=0)return0; vara=1L; varb=1L; for(vari=3;i<=n;i++) { b=checked(a+b); a=b-a; } returnb; }
通用公式法
//////F(n)=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n} /// ////// publicstaticlongCalcD(intn) { if(n<=0)return0; if(n<=2)return1;//加上,可减少运算。 vara=1/Math.Sqrt(5); varb=Math.Pow((1+Math.Sqrt(5))/2,n); varc=Math.Pow((1-Math.Sqrt(5))/2,n); returnchecked((long)(a*(b-c))); }
其他方法
usingSystem; usingSystem.Diagnostics; namespaceFibonacci { classProgram { staticvoidMain(string[]args) { ulongresult; intnumber=10; Console.WriteLine("*************number={0}*************",number); Stopwatchwatch1=newStopwatch(); watch1.Start(); result=F1(number); watch1.Stop(); Console.WriteLine("F1({0})="+result+"耗时:"+watch1.Elapsed,number); Stopwatchwatch2=newStopwatch(); watch2.Start(); result=F2(number); watch2.Stop(); Console.WriteLine("F2({0})="+result+"耗时:"+watch2.Elapsed,number); Stopwatchwatch3=newStopwatch(); watch3.Start(); result=F3(number); watch3.Stop(); Console.WriteLine("F3({0})="+result+"耗时:"+watch3.Elapsed,number); Stopwatchwatch4=newStopwatch(); watch4.Start(); doubleresult4=F4(number); watch4.Stop(); Console.WriteLine("F4({0})="+result4+"耗时:"+watch4.Elapsed,number); Console.WriteLine(); Console.WriteLine("结束"); Console.ReadKey(); } //////迭代法 /// ////// privatestaticulongF1(intnumber) { if(number==1||number==2) { return1; } else { returnF1(number-1)+F1(number-2); } } /// ///直接法 /// ////// privatestaticulongF2(intnumber) { ulonga=1,b=1; if(number==1||number==2) { return1; } else { for(inti=3;i<=number;i++) { ulongc=a+b; b=a; a=c; } returna; } } /// ///矩阵法 /// ////// staticulongF3(intn) { ulong[,]a=newulong[2,2]{{1,1},{1,0}}; ulong[,]b=MatirxPower(a,n); returnb[1,0]; } #regionF3 staticulong[,]MatirxPower(ulong[,]a,intn) { if(n==1){returna;} elseif(n==2){returnMatirxMultiplication(a,a);} elseif(n%2==0) { ulong[,]temp=MatirxPower(a,n/2); returnMatirxMultiplication(temp,temp); } else { ulong[,]temp=MatirxPower(a,n/2); returnMatirxMultiplication(MatirxMultiplication(temp,temp),a); } } staticulong[,]MatirxMultiplication(ulong[,]a,ulong[,]b) { ulong[,]c=newulong[2,2]; for(inti=0;i<2;i++) { for(intj=0;j<2;j++) { for(intk=0;k<2;k++) { c[i,j]+=a[i,k]*b[k,j]; } } } returnc; } #endregion /// ///通项公式法 /// ////// staticdoubleF4(intn) { doublesqrt5=Math.Sqrt(5); return(1/sqrt5*(Math.Pow((1+sqrt5)/2,n)-Math.Pow((1-sqrt5)/2,n))); } } }
OK,就这些了。用的long类型来存储结果,当n>92时会内存溢出。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持毛票票。
声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:czq8825#qq.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。