求斐波那契數列的第n項值——9

    寫一個函數，輸入n，求斐波那契（Fibonacci）數列的第n項。斐波那契數列的定義如下:

         0            n = 0     

   F(n) =  1            n = 1

         F(n-1)+F(n-2)    n > 1

也就是斐波那契數列為{0,1,1,2,3,5,8,13,21，......F(n-1)+F(n-2)}；

    首先可以想到，因為要求第n個斐波那契數，就需要知道第n-1和第n-2個斐波那契數，而求第n-1個斐波那契數就需要知道第n-2個和第n-3個斐波那契數，第n-2個斐波那契數就需要知道第n-3和第n-4個斐波那契數......這樣的話，可以用遞歸來實現：

#include <iostream>
using namespace std;

long long Fib(size_t n)
{
    if(n < 2)
        return n;
    else
        return Fib(n-1)+Fib(n-2);
}

int main()
{
    size_t n = 18; 
    long long ret = Fib(n);
    cout<<"Fibonacci number of "<<n<<" is: "<<ret<<endl;
    return 0;
}

運行程序可得結果：

可以看到第18個斐波那契數為2584，這種情況下是沒什么問題的，但如果將n的值再設大一點的話，比如38，或者48、58，就會發現半天運算不出來結果，這是因為遞歸會有棧的開銷，而一個稍微大點的n就會連續壓十幾個甚至好幾十個棧，這樣的話，系統的運算效率就大大降低了，因此，用遞歸來計算斐波那契數并不是最高效的解法。

    遞歸是不斷地壓棧釋放棧，在每一塊開辟出來的棧中保存有n個斐波那契數，那么，除了用遞歸，也可以用數組來依次存儲從0到n個斐波那契數，用循環來代替棧的開銷，代碼可如下：

long long Fib(size_t n)
{
    if(n < 2)     //當n小于2的時候就可以直接返回效率高，就不必再開辟釋放空間了
        return n;

    long long *p = new long long[n+1];//因為n相當于下標，存在第0個斐波那契數，因此要開辟n+1的大小
    p[0] = 0;
    p[1] = 1;

    for(size_t i = 2; i <= n; ++i)//循環控制條件下標為n的值才是要返回的值
    {
        p[i] = p[i-1] + p[i-2];
    }
    long long ret = p[n];
    delete[] p;//記得釋放空間，否則會有內存泄露
    return ret;
}

運行上面的程序，會發現無論n為多大結果很快就能夠得出來，這樣的運行效率是比遞歸壓棧要高的多的；

    可是，上面的程序還是存在問題，因為如果n的值比較大的話，開辟的空間也會很大，但是我們會發現，要求第n個斐波那契數，只需要知道它前面的兩個數然后相加起來就可以了，也就是說，明明只需要三個數據的空間用來存放數據就好了卻要開辟出很大的一塊空間來將n前面所有的數據都給存放起來，因此，上面的程序雖然比遞歸壓棧效率要高，但是卻比較浪費存儲空間；上面的代碼還是可以優化為如下的：

long long Fib(size_t n)
{
    if(n < 2)
        return n;

    long long f0, f1, f2; //定義三個變量
    f0 = 0;
    f1 = 1;

    for(size_t i = 2; i <= n; ++i)
    {   
        f2 = f0 + f1; //每一次都用三個變量來回交換，因為要求n只需要知道前面兩個數就可以了
        f0 = f1; 
        f1 = f2; 
    }   
    return f2; 
}

《完》