C#实现斐波那契数列整理

 斐波那契数列：｛1,1,2,3,5,8,13,21...｝

1. 递归算法，耗时最长的算法，效率很低。

public static long CalcA(int n)
{
    if (n <= 0) return 0;
    if (n <= 2) return 1;
    return checked(CalcA(n - 2) + CalcA(n - 1));
}

2. 通过循环来实现

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;
}

3. 通过循环的改进写法

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;
}

4. 通用公式法

/// <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时会内存溢出。