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

創新互聯建站專注于企業成都全網營銷、網站重做改版、巴州網站定制設計、自適應品牌網站建設、H5網站設計、商城網站定制開發、集團公司官網建設、成都外貿網站建設公司、高端網站制作、響應式網頁設計等建站業務，價格優惠性價比高，為巴州等各大城市提供網站開發制作服務。

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

《完》

另外有需要云服務器可以了解下創新互聯scvps.cn，海內外云服務器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務器、裸金屬服務器、高防服務器、香港服務器、美國服務器、虛擬主機、免備案服務器”等云主機租用服務以及企業上云的綜合解決方案，具有“安全穩定、簡單易用、服務可用性高、性價比高”等特點與優勢，專為企業上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。

分享文章：求斐波那契數列的第n項值——9-創新互聯
網頁URL：http://vcdvsql.cn/article18/ccsjgp.html

成都網站建設公司_創新互聯，為您提供全網營銷推廣、品牌網站建設、商城網站、定制網站、微信小程序、域名注冊

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯