一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來(lái)。如果所有兔子都不死，起初有一對(duì)小兔子，那么一年以后可以繁殖多少對(duì)兔子？

    舉個(gè)例子，第一個(gè)月小兔子沒(méi)有繁殖能力，所以還是一對(duì)，兩個(gè)月后，生下一對(duì)小兔對(duì)數(shù)共有兩對(duì)，三個(gè)月以后，老兔子又生下一對(duì)，因?yàn)樾⊥米舆€沒(méi)有繁殖能力，所以一共是三對(duì)......

    以此類推我們得到下表

    可以看出幼仔對(duì)數(shù)（從2月起）、成兔對(duì)數(shù)、總體對(duì)數(shù)都構(gòu)成了一個(gè)數(shù)列。這個(gè)數(shù)列有關(guān)十分明顯的特點(diǎn)，那就是：前面相鄰兩項(xiàng)之和，構(gòu)成了后一項(xiàng)。

    這個(gè)數(shù)列是意大利中世紀(jì)數(shù)學(xué)家斐波那契在《算盤全書》中提出的，這就是著名的斐波那契數(shù)列。如果設(shè)F(n）為該數(shù)列的第n項(xiàng)（n∈N*），那么這句話可以寫成如下形式：

F(1)=1，F(xiàn)(2)=1

F(n)=F(n-1)+F(n-2)（n≥3，n∈N*）

我們除了可以用上面的遞推式計(jì)算出斐波那契數(shù)列的每一項(xiàng)，我們還可以直接使用通項(xiàng)公式

至于有關(guān)它的推導(dǎo)主要有兩種，一種是利用特征方程，另一種是待定系數(shù)法構(gòu)建等比數(shù)列。具體的推導(dǎo)過(guò)程在這里就不贅述了。

    斐波那契數(shù)列中的斐波那契數(shù)會(huì)經(jīng)常出現(xiàn)在我們的眼前——比如松果、鳳梨、樹(shù)葉的排列、某些花朵的花瓣數(shù)（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀等等。斐波那契數(shù)還可以在植物的葉、枝、莖等排列中發(fā)現(xiàn)。

    大自然里一些花草長(zhǎng)出的枝條經(jīng)常會(huì)出現(xiàn)斐波那契數(shù)，新的一枝從葉腋長(zhǎng)出，而另外的新枝又從舊枝長(zhǎng)出來(lái)，老枝條和新枝條的數(shù)目的和就像那兔子問(wèn)題一樣。

（下面兩段內(nèi)容選擇閱讀）

    仔細(xì)觀察向日葵的花，可以看到，向日葵花盤內(nèi)，種子是按對(duì)數(shù)螺線排列的，有順時(shí)針轉(zhuǎn)和逆時(shí)針轉(zhuǎn)的兩組對(duì)數(shù)螺線。兩組螺線的條數(shù)往往成相繼的兩個(gè)斐波那契數(shù)，一般是34和55，大向日葵是89和144，還曾發(fā)現(xiàn)過(guò)一個(gè)更大的向日葵有144和233條螺線，它們都是相繼的兩個(gè)斐波那契數(shù)。

    常見(jiàn)的花瓣還有3瓣的鳶尾花（看上去是6片花瓣，實(shí)際上是兩組3瓣），8瓣的飛燕草，13瓣的翠雀花等等。

    斐波那契數(shù)列有關(guān)的數(shù)學(xué)問(wèn)題可有點(diǎn)多，比如楊輝三角、黃金分割、排列組合、矩形面積、質(zhì)數(shù)數(shù)量、尾數(shù)循環(huán)等等。

    其中黃金分割比較簡(jiǎn)單，在這里說(shuō)一下，隨著數(shù)列項(xiàng)數(shù)的增加，前一項(xiàng)與后一項(xiàng)之比越來(lái)越逼近黃金分割的數(shù)值0.6180339887..…

    今天我們只考慮一個(gè)楊輝三角問(wèn)題（原因是這個(gè)問(wèn)題似乎比起其他幾個(gè)好像更接近程序設(shè)計(jì)）。這一期主要還是說(shuō)斐波那契數(shù)列的，所以楊輝三角我們只說(shuō)一下他們之間的聯(lián)系。

楊輝三角的第一行只有一個(gè)數(shù)為1，接下來(lái)每一行都比上一行要多一個(gè)數(shù)，每個(gè)數(shù)等于它上方兩數(shù)之和。

在這張圖里相信大家已經(jīng)發(fā)現(xiàn)了斐波那契數(shù)列，就是每條虛線上數(shù)字的和，但這樣似乎不夠明顯，那我們把楊輝三角每一行的左端對(duì)齊。

這次是不是思路清晰多了。

1.一般而言，兔子在出生兩個(gè)月后，就有繁殖能力，一對(duì)兔子每個(gè)月能生出一對(duì)小兔子來(lái)。如果所有兔子都不死，起初有一對(duì)小兔子，那么X個(gè)月以后可以繁殖多少對(duì)兔子？

    這個(gè)就是開(kāi)篇的兔子數(shù)列，我們就直接略過(guò)了吧。

2.蜜蜂路線

1. 一維變形

    如果上面的爬樓梯問(wèn)題每步可以上1-3階呢？那1-4階呢？同樣的我們只需要數(shù)好前幾階共有幾種方案，之后的每階的方案數(shù)就是這階前3或4方案數(shù)之和。

    2.二維變形

    過(guò)河卒（NOIP2002普及組）（洛谷P1002）

類似地，想要走到一個(gè)格子里只能從這個(gè)格子的上方或左方進(jìn)入，依次遞推出結(jié)果就好了。

1.遞歸

int fib(int N) {        

    if(N < 2)

        return N;       

    return fib(N - 1) + fib(N - 2);   

}

2.遞推

int fib(int N) {       

    int dp[MAXN];        

    if(N == 0)

         return 0;       

    dp[0] = 0; dp[1] = 1;

    for(int i = 2; i <= N; i ++){

          dp[i] = dp[i - 1] + dp[i - 2];       

    }       

    return dp[N];   

}

3.迭代（模擬）

int fib(int N) {        

    if(N < 2) return N;        

    int a = 0; 

    int b = 1; 

    int c = 0;       

    for(int i = 2; i <= N; i ++){

          c = a + b;

          a = b; 

          b = c;       

    }       

    return c;   

}