C#实现斐波那契数列的几种方法整理

2023-09-08 03:18:05 354

什么是斐波那契数列？经典数学问题之一；斐波那契数列，又称黄金分割数列，指的是这样一个数列：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（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。

C#实现斐波那契数列的几种方法整理

热门推荐

随机推荐