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

創(chuàng)新互聯(lián)建站專注于企業(yè)成都全網(wǎng)營銷、網(wǎng)站重做改版、巴州網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5網(wǎng)站設(shè)計、商城網(wǎng)站定制開發(fā)、集團公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為巴州等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

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

《完》

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

分享文章：求斐波那契數(shù)列的第n項值——9-創(chuàng)新互聯(lián)
網(wǎng)頁URL：http://jinyejixie.com/article18/ccsjgp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供全網(wǎng)營銷推廣、品牌網(wǎng)站建設(shè)、商城網(wǎng)站、定制網(wǎng)站、微信小程序、域名注冊

廣告

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