斐波那契数列：｛1,1,2,3,5,8,13,21...｝
- 递归算法，耗时最长的算法，效率很低。
public static long CalcA(int n)
{
if (n <= 0) return 0;
if (n <= 2) return 1;
return checked(CalcA(n - 2) + CalcA(n - 1));
}
- 通过循环来实现
public static long CalcB(int n)
{
if (n <= 0) return 0;
var a = 1L;
var b = 1L;
var result = 1L;
for (var i = 3; i <= n; i++)
{
result = checked(a + b);
a = b;
b = result;
}
return result;
}
- 通过循环的改进写法
public static long CalcC(int n)
{
if (n <= 0) return 0;
var a = 1L;
var b = 1L;
for (var i = 3; i <= n; i++)
{
b = checked(a + b);
a = b - a;
}
return b;
}
- 通用公式法
/// <summary>
/// F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static long CalcD(int n)
{
if (n <= 0) return 0;
if (n <= 2) return 1; //加上，可减少运算。
var a = 1 / Math.Sqrt(5);
var b = Math.Pow((1 + Math.Sqrt(5)) / 2, n);
var c = Math.Pow((1 - Math.Sqrt(5)) / 2, n);
return checked((long)(a * (b - c)));
}
OK，就这些了。用的long类型来存储结果，当n>92时会内存溢出。
