fibonacci數(shù)列為什么那么重要，所有關(guān)于數(shù)學的書幾乎都會提到？

pphsy 2015-02-16

展開全文

一句話先回答問題：因為斐波那契數(shù)列在數(shù)學和生活以及自然界中都非常有用。

下面我就盡我所能，講述一下斐波那契數(shù)列。

一、起源和定義

斐波那契數(shù)列最早被提出是印度數(shù)學家Gopala，他在研究箱子包裝物件長度恰好為1和2時的方法數(shù)時首先描述了這個數(shù)列。也就是這個問題：

有n個臺階，你每次只能跨一階或兩階，上樓有幾種方法？

而最早研究這個數(shù)列的當然就是斐波那契（Leonardo Fibonacci）了，他當時是為了描述如下情況的兔子生長數(shù)目：

第一個月初有一對剛誕生的兔子
第二個月之后（第三個月初）它們可以生育
每月每對可生育的兔子會誕生下一對新兔子
兔子永不死去

這個數(shù)列出自他赫赫有名的大作《計算之書》（沒有維基詞條，坑），后來就被廣泛的應(yīng)用于各種場合了。這個數(shù)列是這么定義的：

The On-Line Encyclopedia of Integer Sequences? (OEIS?)序號為A000045 - OEIS

（注意，并非滿足第三條的都是斐波那契數(shù)列，盧卡斯數(shù)列（A000032 - OEIS）也滿足這一特點，但初始項定義不同）

二、求解方法

講完了定義，再來說一說如何求對應(yīng)的項。斐波那契數(shù)列是編程書中講遞歸必提的，因為它是按照遞歸定義的。所以我們就從遞歸開始講起。

1.遞歸求解

int Fib(int n)
{
return n < 2 ? 1 : (Fib(n-1) + Fib(n-2));
}

這是編程最方便的解法，當然，也是效率最低的解法，原因是會出現(xiàn)大量的重復計算。為了避免這種情況，可以采用遞推的方式。

2.遞推求解

int Fib[1000];
Fib[0] = 0;Fib[1] = 1;
for(int i = 2;i < 1000;i++) Fib[i] = Fib[i-1] + Fib[i-2];

遞推的方法可以在O(n)的時間內(nèi)求出Fib(n)的值。但是這實際還是不夠好，因為當n很大時這個算法還是無能為力的。接下來就要來講一個有意思的東西：矩陣。

3.矩陣遞推關(guān)系

學過代數(shù)的人可以看出，下面這個式子是成立的：

不停地利用這個式子迭代右邊的列向量，會得到下面的式子：

這樣，問題就轉(zhuǎn)化為如何計算這個矩陣的n次方了，可以采用快速冪的方法。快速冪_百度百科是利用結(jié)合律快速計算冪次的方法。比如我要計算 $2^{20}$ ，我們知道 $2^{20} = 2^{16} * 2^{4}$ ，而 $2^{2}$ 可以通過 $2^{1} \times 2^{1}$ 來計算， $2^{4}$ 而可以通過 $2^{2}\times 2^{2}$ 計算，以此類推。通過這種方法，可以在O（lbn）的時間里計算出一個數(shù)的n次冪。快速冪的代碼如下：

int Qpow(int a,int n)
{
    int ans = 1;
    while(n)
    {
        if(n&1) ans *= a;
        a *= a;
        n >>= 1;
    }
    return ans;
}

將上述代碼中的整型變量a變成矩陣，數(shù)的乘法變成矩陣乘法，就是矩陣快速冪了。比如用矩陣快速冪計算斐波那契數(shù)列：

#include <cstdio>
#include <iostream>

using namespace std;

const int MOD = 10000;

struct matrix//定義矩陣結(jié)構(gòu)體
{
    int m[2][2];
}ans, base;

matrix multi(matrix a, matrix b)//定義矩陣乘法
{
    matrix tmp;
    for(int i = 0; i < 2; ++i)
    {
        for(int j = 0; j < 2; ++j)
        {
            tmp.m[i][j] = 0;
            for(int k = 0; k < 2; ++k)
                tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
        }
    }
    return tmp;
}
int fast_mod(int n)  // 求矩陣 base 的  n 次冪 
{
    base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
    base.m[1][1] = 0;
    ans.m[0][0] = ans.m[1][1] = 1;  // ans 初始化為單位矩陣 
    ans.m[0][1] = ans.m[1][0] = 0;
    while(n)
    {
        if(n & 1)  //實現(xiàn) ans *= t; 其中要先把 ans賦值給 tmp，然后用 ans = tmp * t 
            ans = multi(ans, base);

        base = multi(base, base);
        n >>= 1;
    }
    return ans.m[0][1];
}

int main()
{
    int n;
    while(scanf("%d", &n) && n != -1)
    {   
        printf("%d\n", fast_mod(n));
    }
    return 0;
}

4.通項公式

無論如何，對于一個數(shù)列，我們都是希望可以建立 F(n)

與n的關(guān)系，也就是通項公式，而用不同方法去求解通項公式也是很有意思的。

（1）構(gòu)造等比數(shù)列

設(shè) $f(n) + \alpha f(n-1) = \beta [f(n-1) + \alpha f(n-2)]$ ,
化簡得 $f(n)=(\beta -\alpha )f(n-1)+\alpha \beta f(n-2)$ ,
比較系數(shù)得 $\beta -\alpha =1,\alpha \beta =1$ ，
解得 $\alpha =\frac{\sqrt{5}-1 }{2}$ ， $\beta =\frac{\sqrt{5}+1 }{2}$
由于 $f(n+1)+\alpha f(n)=[f(2)+\alpha f(1)]\beta ^{n-1} =\beta ^{n}$
故有 $\frac{f(n+1)}{\beta ^{n+1}} +\frac{\alpha}{\beta } \frac{f(n)}{\beta ^{n} } =\frac{1}{\beta }$ ，設(shè) $g(n)=\frac{f(n)}{\beta ^{n}}$ .則有
$g(n+1)+\frac{\alpha }{\beta } g(n)=\frac{1}{\beta }$ ,設(shè) $g(n+1)+\lambda =-\frac{\alpha }{\beta } (g(n)+\lambda )$ ,
解得 $\lambda =-\frac{1}{\alpha +\beta }$ ，即{ $g(n)+\lambda$ }是等比數(shù)列。這樣就有
$g(n)+\lambda=(-\frac{\alpha }{\beta } )^{n-1} (\frac{1}{\beta } +\lambda )$
到了現(xiàn)在，把上述解出的結(jié)果全部帶入上式，稍作變形，我們就可以寫出斐波那契數(shù)列的通項公式了

$f(n)=\frac{1}{\sqrt{5} } [(\frac{1+\sqrt{5} }{2} )^{n}-(\frac{1-\sqrt{5} }{2} )^{n}]$

這個方法還是比較麻煩的，但是非?；A(chǔ)。事實上還有其他更簡單的方法。

（2）線性代數(shù)解法
這個解法首先用到

公式，如果可以找到矩陣

使得 $PAP^{-1}$ 為對角陣，我們就可以求出通項。下面需要一些高等代數(shù)知識，沒學過的可直接跳過。
首先令 $|\lambda E-A|=0$ ,解得兩個特征根
$\lambda_{1}=\frac{1-\sqrt{5} }{2} , \lambda_{2}=\frac{1+\sqrt{5} }{2}$
兩個特征向量為
$\alpha _{1}=[1,\frac{1+\sqrt{5} }{2} ] ^{T},\alpha _{2}=[1,\frac{-1+\sqrt{5} }{2} ] ^{T},$ 則

而解出 $A^{n}=P^{-1}(PAP^{-1})^{n}P$ ,中間矩陣的n次方可以直接求出來：

然后可以輕易得到通項公式，上邊已經(jīng)給出，這里不再贅述。

（3）特征方程解法

通過方法（2），我們可以推導出一般的線性遞推數(shù)列的通項求解方法，也就是特征方程法。我們可以發(fā)現(xiàn)，對于這種數(shù)列，通項總是可以表示為 $f(n)=C_{1} \lambda _{1}^{n} +C_{2} \lambda _{2}^{n}$ 的形式，因此可以直接利用已知項求解 $C_{1}$ ， $C_{2}$ 。具體做法如下：

a.由遞推數(shù)列構(gòu)造特征方程 $x^{2}=x+1$ ，解出兩個特征值 $\lambda_{1}=\frac{1-\sqrt{5} }{2} , \lambda_{2}=\frac{1+\sqrt{5} }{2}$ 。

b.帶入 f(0),f(1)

,列出如下方程：

$C_{1} +C_{1} =0$
$\frac{1-\sqrt{5} }{2} C_{1} +\frac{1+\sqrt{5} }{2} C_{2} =1$

解得 $C_{1} =-\frac{1}{\sqrt{5} } ,C_{2} =\frac{1}{\sqrt{5} } .$ 這樣直接寫出通項公式，是比較簡單的做法。

（4）母函數(shù)法（此方法涉及組合數(shù)學知識）

設(shè)斐波那契數(shù)列的母函數(shù)為 G(x)

,即
$G(x)=F_{0} +F_{1}x+F_{2}x^{2}+L+F_{n}x^{n}$
$=1+x+(F_{0}+F_{1})x^{2}+L+(F_{n-1} +F_{n-2})x^{n}$
$=1+(x+F_{1}x^{2}+F_{2}x^{3}+L+)+(F_{0}x^{2}+F_{1}x^3+L)$
$=1+(x+x^{2})G(x)$
解得 $G(x)=\frac{1}{1-x-x^{2}} =\frac{1}{\sqrt{5} } \frac{1+\sqrt{5} }{2}\frac{1}{1-\frac{1+\sqrt{5} }{2}x} -\frac{1}{\sqrt{5} } \frac{1-\sqrt{5} }{2}\frac{1}{1-\frac{1-\sqrt{5} }{2}x}$

再由冪級數(shù)展開公式 $\frac{1}{1-x}=1+x+x^{2}+$ ……

合并同類項并與 G(x)

的系數(shù)比較即可。

到這里，求解斐波那契數(shù)列通項的方法就說的差不多了。無論是計算機求解還是數(shù)學推導，都體現(xiàn)出了非常多的技巧。而斐波那契數(shù)列的許多特性，就更加有意思了。

三、斐波那契數(shù)列的數(shù)學性質(zhì)

1.與黃金比的關(guān)系

由通項公式，求相鄰兩項的商的極限，結(jié)果是黃金比，所以斐波那契數(shù)列又稱為黃金比數(shù)列。斐波那契數(shù)列和黃金比還和一個有趣的數(shù)學概念——連分數(shù)有關(guān)：

2.一些簡單的規(guī)律

（1）任意連續(xù)四個斐波那契數(shù)，可以構(gòu)造出一個畢達哥拉斯三元組。如取1,1,2,3.
中間兩數(shù)相乘再乘2 ==》 4
外層2數(shù)乘積==》3
中間兩數(shù)平方和==》5
得到3,4,5.
下一組是5,12,13,，有興趣的讀者可以再試著推一推，證明也是容易的。

（2）整除性

每3個連續(xù)的斐波那契數(shù)有且只有一個被2整除，

每4個連續(xù)的斐波那契數(shù)有且只有一個被3整除，

每5個連續(xù)的斐波那契數(shù)有且只有一個被5整除，

每6個連續(xù)的斐波那契數(shù)有且只有一個被8整除，

每7個連續(xù)的斐波那契數(shù)有且只有一個被13整除，

…………

每n個連續(xù)的斐波那契數(shù)有且只有一個被 f(n) 整除.

（3）一些恒等式

3.楊輝三角中的斐波那契數(shù)列

如圖所示，每條斜線上的數(shù)的和就構(gòu)成斐波那契數(shù)列。

即有 $f(n)=C_{n-1}^{0} +C_{n-2}^{1}+L+C_{n-1-m}^{m}$

4.相關(guān)數(shù)列：盧卡斯（Lucas）數(shù)列

盧卡斯數(shù)列的定義除了第0項為2之外，與斐波那契數(shù)列完全一致。即

其通項公式為：

盧卡斯數(shù)列和斐波那契數(shù)列有這些關(guān)系：

$F_{2n}=F_{n}L_{n}$
$5F_{n}=L_{n-1}+L_{n+1}$
$L_{n}^{2}=5 F_{n}^{2}+4(-1)^{n}$
$\lim_{n \rightarrow \infty }{\frac{L_{n}}{F_{n}} } =\sqrt{5}$
$L_{n}=F_{n-1}+F_{n+1}$

5.組合數(shù)學

（1）一些恒等式

（2）同余特性

$F(m)|F(n)\Leftrightarrow m|n$

當p為大于5的素數(shù)時，有：

$F(p-(\frac{p}{5}))\equiv 0(modp)$
$F(p)\equiv (\frac{p}{5}) (modp)$
$F(p+(\frac{p}{5}))\equiv 1(modp)$

其中

斐波那契數(shù)列還有許許多多的性質(zhì)，我就不再一一介紹了。跑題了這么久，終于開始要真正回答問題了：斐波那契數(shù)列有什么用？

四、斐波那契數(shù)列的應(yīng)用

1.算法

a.斐波那契堆

斐波那契堆(Fibonacci heap)是計算機科學中最小堆有序樹的集合。它和二項式堆有類似的性質(zhì)，可用于實現(xiàn)合并優(yōu)先隊列。特點是不涉及刪除元素的操作有O(1)的平攤時間，用途包括稠密圖每次Decrease－key只要O(1)的平攤時間，和二項堆的O(lgn)相比是巨大的改進。

斐波那契堆由一組最小堆構(gòu)成，這些最小堆是有根的無序樹?？梢赃M行插入、查找、合并和刪除等操作
1）插入：創(chuàng)建一個僅包含一個節(jié)點的新的斐波納契堆，然后執(zhí)行堆合并
2）查找：由于用一個指針指向了具有最小值的根節(jié)點，因此查找最小的節(jié)點是平凡的操作。
3）合并：簡單合并兩個斐波納契堆的根表。即把兩個斐波納契堆的所有樹的根首尾銜接并置。
4）刪除（釋放）最小節(jié)點
分為三步：
查找最小的根節(jié)點并刪除它，其所有的子節(jié)點都加入堆的根表，即它的子樹都成為堆所包含的樹；
需要查找并維護堆的最小根節(jié)點，但這耗時較大。為此，同時完成堆的維護：對堆當前包含的樹的度數(shù)從低到高，迭代執(zhí)行具有相同度數(shù)的樹的合并并實現(xiàn)最小樹化調(diào)整，使得堆包含的樹具有不同的度數(shù)。這一步使用一個數(shù)組，數(shù)組下標為根節(jié)點的度數(shù)，數(shù)組的值為指向該根節(jié)點指針。如果發(fā)現(xiàn)具有相同度數(shù)的其他根節(jié)點則合并兩棵樹并維護該數(shù)組的狀態(tài)。
對當前堆的所有根節(jié)點查找最小的根節(jié)點。
5）降低一個點的鍵值：對一個節(jié)點的鍵值降低后，自鍵值降低的節(jié)點開始自下而上的迭代執(zhí)行下述操作，直至到根節(jié)點或一個未被標記（marked）節(jié)點為止：
如果當前節(jié)點鍵值小于其父節(jié)點的鍵值，則把該節(jié)點及其子樹摘下來作為堆的新樹的根節(jié)點；其原父節(jié)點如果是被標記（marked）節(jié)點，則也被摘下來作為堆的新樹的根節(jié)點；如果其原父節(jié)點不是被標記（marked）節(jié)點且不是根節(jié)點，則其原父節(jié)點被加標記。
如果堆的新樹的根節(jié)點被標記（marked），則去除該標記。
6）刪除節(jié)點：把被刪除節(jié)點的鍵值調(diào)整為負無窮小，然后執(zhí)行“降低一個節(jié)點的鍵值”算法，然后再執(zhí)行“刪除最小節(jié)點”算法。
斐波那契堆

b.歐幾里得算法的時間復雜度

歐幾里得算法是求解兩個正整數(shù)最大公約數(shù)的算法，又稱輾轉(zhuǎn)相除法。代碼如下：

int gcd(int a,int b)
{
    return b ? gcd(b,a%b) : a;
}

在最壞的情況下，我們可以證明，若a較小，需要計算的次數(shù)為n，則 a>F(n-1)

.雖然說一般分析的時候會當成對數(shù)階，但數(shù)論最常用的歐幾里得算法竟然與斐波那契數(shù)列有關(guān)，也確實是很讓人吃驚呢。

2.物理學：氫原子能級問題

假定我們現(xiàn)在有一些氫氣原子，一個電子最初所處的位置是最低的能級（Ground lever of energy），屬于穩(wěn)定狀態(tài)。它能獲得一個能量子或二個能量子（Quanta of energy）而使它上升到第一能級或者第二能級。但是在第一級的電子如失掉一個能量子就會下降到最低能級，它如獲得一個能量子就會上升到第二級來。

現(xiàn)在研究氣體吸收和放出能量的情形，假定最初電子是處在穩(wěn)定狀態(tài)即零能級，然后讓它吸收能量，這電子可以跳到第1能級或第2能級。然后再讓這氣體放射能量，這時電子在1級能級的就要下降到0能級，而在第2能級的可能下降到0能級或者第1能級的位置去。

電子所處的狀態(tài)可能的情形是：1、2、3、5、8、13、21…種。這是斐波那契數(shù)列的一部份。

3.自然界：植物的生長

科學家發(fā)現(xiàn)，一些植物的花瓣、萼片、果實的數(shù)目以及排列的方式上，都有一個神奇的規(guī)律，它們都非常符合著名的斐波那契數(shù)列。例如：薊，它們的頭部幾乎呈球狀。在下圖中，你可以看到兩條不同方向的螺旋。我們可以數(shù)一下，順時針旋轉(zhuǎn)的（和左邊那條旋轉(zhuǎn)方向相同）螺旋一共有13條，而逆時針旋轉(zhuǎn)的則有21條。此外還有菊花、向日葵、松果、菠蘿等都是按這種方式生長的。

還有菠蘿、松子等，也都符合這個特點，一般會出現(xiàn)34,55，89和144這幾個數(shù)字。

最后上一張“斐波那契樹”的圖片：

是的，這玩意就長這樣，這種植物是存在的。

4.波浪理論與股市

這個答主不懂，大家可自行閱讀文章波浪理論斐波那契數(shù)列與黃金分割率。
不過波浪的形狀確實符合下邊要說的斐波那契螺旋：

5.斐波那契螺旋

斐波那契螺旋又稱黃金螺旋，在自然界中廣泛存在。如圖是一個邊長為斐波那契數(shù)列的正方形組成的矩形。

（加一句：看著這個圖，是不是能發(fā)現(xiàn)

是顯而易見的？）

這樣連起來就是斐波那契螺旋了

貝殼螺旋輪廓線

向日葵的生長

神奇的花

6.建筑學

7.據(jù)說一個小男孩參考斐波那契數(shù)列發(fā)明了太陽能電池樹：

一名13歲的男孩根據(jù)斐波那契數(shù)列發(fā)明了太陽能電池樹，其產(chǎn)生的電力比太陽能光伏電池陣列多20-50%。斐波那契數(shù)列類似從0和1開始，之后的數(shù)是之前兩數(shù)的和，如0，1，1，2，3，5，8，13，21...Aidan Dwye在觀察樹枝分叉時發(fā)現(xiàn)它的分布模式類似斐波那契數(shù)列，這是大自然演化的一種結(jié)果，可能有助于樹葉進行光合作用。
因此，Dwye猜想為什么不按照斐波那契數(shù)列排列太陽能電池？他設(shè)計了太陽能電池樹，發(fā)現(xiàn)它的輸出電力提高了20%，每天接受光照的時間延長了2.5小時。

8.斐波那契螺旋形的搖椅

媽媽搖椅是設(shè)計師Patrick Messier為自己的妻子兼合作伙伴Sophie Fournier設(shè)計的，當時他們剛有了第一個寶寶。
當Sophie宣布自己懷孕時，她說想要一把搖椅，但發(fā)現(xiàn)沒有一把搖椅能滿足美觀舒適的標準，于是Patrick決定自己做一把。
于是就有了這把媽媽搖椅。像是一個飄在空中的絲帶，由一片纖維玻璃做成，曲線服從斐波那契數(shù)列分布，經(jīng)過特殊的高光聚氨酯處理。

五、數(shù)學上的擴展

（1）廣義斐波那契數(shù)列
定義： $a+b,ab\in Z$ ,數(shù)列 f(n)

滿足：

其通項為：

當

時即為斐波那契數(shù)列。

（2）反斐波那契數(shù)列

定義： g(n+2)=g(n)-g(n+1)

反斐波那契數(shù)列相鄰項比值的極限為 -0.618

。

（3）巴都萬數(shù)列(A000931 - OEIS)
斐波那契數(shù)列可以刻畫矩形，而巴都萬數(shù)列則刻畫的是三角形。其定義如下：

(4)未解之謎：角谷猜想

對一個正整數(shù)，若為奇數(shù)則乘3加1，若為奇數(shù)則除以2，通過有限次這樣的操作，能否使得該數(shù)變成1？
這個猜想和斐波那契數(shù)列又很大關(guān)系，具體的可以看角谷猜想的斐波那契數(shù)列現(xiàn)象。

六、總結(jié)

斐波那契數(shù)列是各個學科中都出現(xiàn)的小滑頭，它許多漂亮的性質(zhì)讓我們著迷。上文我所描述的這些只是它的冰山一角，權(quán)當拋磚引玉。大家讀完了我的答案，還可以再結(jié)合自己的專業(yè)去看一些相關(guān)的資料，更好的去了解這個有趣的數(shù)列。

七、參考文獻