求斐波那契數(shù)列的第n項值——9

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

         0            n = 0     

   F(n) =  1            n = 1

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

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

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

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

運行程序可得結(jié)果：

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

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

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

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

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

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

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

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只需要知道前面兩個數(shù)就可以了
        f0 = f1; 
        f1 = f2; 
    }   
    return f2; 
}

《完》