菲波那切數(shù)列*

1.引入
斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列、因數(shù)學(xué)家列昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞推的方法定義：F(1)=1，F(xiàn)(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）在現(xiàn)代物理、準(zhǔn)晶體結(jié)構(gòu)、化學(xué)等領(lǐng)域，斐波納契數(shù)列都有直接的應(yīng)用，為此，美國數(shù)學(xué)會(huì)從1963年起出版了以《斐波納契數(shù)列季刊》為名的一份數(shù)學(xué)雜志，用于專門刊載這方面的研究成果。

10年積累的網(wǎng)站設(shè)計(jì)制作、做網(wǎng)站經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站策劃后付款的網(wǎng)站建設(shè)流程，更有梅里斯免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

2.定義
斐波那契數(shù)列指的是這樣一個(gè)數(shù)列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368
........這個(gè)數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。
斐波那契數(shù)列的定義者，是意大利數(shù)學(xué)家列昂納多·斐波那契（Leonardo Fibonacci），生于公元1170年，卒于1250年，籍貫是比薩。他被人稱作“比薩的列昂納多”。1202年，他撰寫了《算盤全書》（Liber Abacci）一書。他是第一個(gè)研究了印度和阿拉伯?dāng)?shù)學(xué)理論的歐洲人。他的父親被比薩的一家商業(yè)團(tuán)體聘任為外交領(lǐng)事，派駐地點(diǎn)于阿爾及利亞地區(qū)，列昂納多因此得以在一個(gè)阿拉伯老師的指導(dǎo)下研究數(shù)學(xué)。他還曾在埃及、敘利亞、希臘、西西里和普羅旺斯等地研究數(shù)學(xué)。
3.求解

1. 遞歸方法

根據(jù)這個(gè)公式，應(yīng)用遞歸調(diào)用可以很好的求解菲波那切數(shù)列第N項(xiàng)，以下為求解過程（源代碼）：

#include
#include
int fib(int n)
{
    if (n <= 2)
        return  1;
    else 
        return  fib(n - 1) + fib(n - 2);
}
int main()
{
    int n = 0;
    int ret = 0;

    scanf("%d",&n);
    ret = fib(n);
    printf("%d\n", ret);
    system("pause");

    return 0;
}

我們?cè)隍?yàn)證前幾個(gè)菲波那切數(shù)列都沒有問題，但是這樣就完了嗎？不，其實(shí)再往下走，比如給個(gè)50他就算不出來了。這是為什么呢，仔細(xì)想想就不難發(fā)現(xiàn)：原來每次遞歸調(diào)用都會(huì)把一個(gè)值重復(fù)算好多遍，我們用個(gè)例子來驗(yàn)證一下：

#include
#include
int count = 0;
int fib(int n)
{

    if (n == 3)
        count++;
    if (n <= 2)
        return  1;
    else 
        return  fib(n - 1) + fib(n - 2);
}
int main()
{
    int n = 0;
    int ret = 0;

    scanf("%d",&n);
    ret = fib(n);
    printf("%d\n", ret);
    printf("%d\n", count);
    system("pause");

    return 0;
}

這個(gè)代碼輸出結(jié)果為

這里我們定義一個(gè)全局變量count，這里只僅僅計(jì)算了fib(3)被重復(fù)計(jì)算的次數(shù)就已經(jīng)這么大了，可想而知這個(gè)代碼輸入的N值一旦很大計(jì)算效率就會(huì)變得極其差，那么怎么解決這個(gè)問題呢，下面在引進(jìn)一個(gè)方法：

2.非遞歸——迭代（即循環(huán)）

我們?cè)趺醋瞿兀褪沁@樣：前三個(gè)菲波那切數(shù)我們知道，我們可不可以利用迭代來計(jì)算后面的斐波那契數(shù)呢，顯然是可以的。我們可以這樣想：首先讓a=1,b=1我們讓c=a+b然后利用循環(huán)來交換a，b，c的值不就好了?？墒侨绾螌?shí)現(xiàn)呢，以下分享一下我的想法：

#include
#include
int fib(int n)
{
    int a = 1;
    int b = 1;
    int c = 0;
    while (n > 2)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    return c;
}
int main()
{
    int n = 0;
    int ret = 0;

    scanf("%d",&n);
    ret = fib(n);
    printf("%d\n", ret);
    system("pause");

    return 0;
}

這個(gè)思想可以這樣實(shí)現(xiàn)，可是又出現(xiàn)一個(gè)問題，當(dāng)n太大時(shí)數(shù)存不下來，從而導(dǎo)致計(jì)算可能有點(diǎn)問題，所以還是需要大佬們來完善一下?？墒沁@個(gè)的效率絕對(duì)比上面的遞歸方法要高很多，這個(gè)計(jì)算比較小的n還是挺快的。
這里我們看到有些問題可以用遞歸去做，但是不適用遞歸解決它，否則只會(huì)適得其反。希望在小伙伴們的評(píng)論區(qū)里找到更好的解決辦法哦。