斐波那契數(shù)列

一句話先回答問(wèn)題：因?yàn)殪巢瞧鯏?shù)列在數(shù)學(xué)和生活以及自然界中都非常有用。

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

一、起源和定義

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

有n個(gè)臺(tái)階，你每次只能跨一階或兩階，上樓有幾種方法？

而最早研究這個(gè)數(shù)列的當(dāng)然就是斐波那契（LeonardoFibonacci）了，他當(dāng)時(shí)是為了描述如下情況的兔子生長(zhǎng)數(shù)目：

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

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

TheOn-LineEncyclopediaofIntegerSequences?(OEIS?)序號(hào)為A000045-OEIS

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

二、求解方法

講完了定義，再來(lái)說(shuō)一說(shuō)如何求對(duì)應(yīng)的項(xiàng)。斐波那契數(shù)列是編程書(shū)中講遞歸必提的，因?yàn)樗前凑者f歸定義的。所以我們就從遞歸開(kāi)始講起。

1.遞歸求解

intFib(intn){returnn<2?1:(Fib(n-1)+Fib(n-2));}

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

2.遞推求解

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

遞推的方法可以在O(n)的時(shí)間內(nèi)求出Fib(n)的值。但是這實(shí)際還是不夠好，因?yàn)楫?dāng)n很大時(shí)這個(gè)算法還是無(wú)能為力的。接下來(lái)就要來(lái)講一個(gè)有意思的東西：矩陣。

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

學(xué)過(guò)代數(shù)的人可以看出，下面這個(gè)式子是成立的：不停地利用這個(gè)式子迭代右邊的列向量，會(huì)得到下面的式子：這樣，問(wèn)題就轉(zhuǎn)化為如何計(jì)算這個(gè)矩陣的n次方了，可以采用快速冪的方法。快速冪_百度百科是利用結(jié)合律快速計(jì)算冪次的方法。比如我要計(jì)算，我們知道，而可以通過(guò)來(lái)計(jì)算，而可以通過(guò)計(jì)算，以此類推。通過(guò)這種方法，可以在O（lbn）的時(shí)間里計(jì)算出一個(gè)數(shù)的n次冪?？焖賰绲拇a如下：intQpow(inta,intn){intans=1;while(n){if(n&1)ans*=a;a*=a;n>>=1;}returnans;}將上述代碼中的整型變量a變成矩陣，數(shù)的乘法變成矩陣乘法，就是矩陣快速冪了。比如用矩陣快速冪計(jì)算斐波那契數(shù)列：#include<cstdio>#include<iostream>usingnamespacestd;constintMOD=10000;structmatrix//定義矩陣結(jié)構(gòu)體{intm[2][2];}ans,base;matrixmulti(matrixa,matrixb)//定義矩陣乘法{matrixtmp;for(inti=0;i<2;++i){for(intj=0;j<2;++j){tmp.m[i][j]=0;for(intk=0;k<2;++k)tmp.m[i][j]=(tmp.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;}}returntmp;}intfast_mod(intn)//求矩陣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)//實(shí)現(xiàn)ans*=t;其中要先把a(bǔ)ns賦值給tmp，然后用ans=tmp*tans=multi(ans,base);base=multi(base,base);n>>=1;}returnans.m[0][1];}intmain(){intn;while(scanf("%d",&n)&&n!=-1){printf("%d\n",fast_mod(n));}return0;}4.通項(xiàng)公式無(wú)論如何，對(duì)于一個(gè)數(shù)列，我們都是希望可以建立與n的關(guān)系，也就是通項(xiàng)公式，而用不同方法去求解通項(xiàng)公式也是很有意思的。（1）構(gòu)造等比數(shù)列設(shè),化簡(jiǎn)得,比較系數(shù)得，解得，由于故有，設(shè).則有,設(shè),解得，即{}是等比數(shù)列。這樣就有到了現(xiàn)在，把上述解出的結(jié)果全部帶入上式，稍作變形，我們就可以寫(xiě)出斐波那契數(shù)列的通項(xiàng)公式了這個(gè)方法還是比較麻煩的，但是非?；A(chǔ)。事實(shí)上還有其他更簡(jiǎn)單的方法。（2）線性代數(shù)解法這個(gè)解法首先用到公式，如果可以找到矩陣使得為對(duì)角陣，我們就可以求出通項(xiàng)。下面需要一些高等代數(shù)知識(shí)，沒(méi)學(xué)過(guò)的可直接跳過(guò)。首先令,解得兩個(gè)特征根兩個(gè)特征向量為則而解出,中間矩陣的n次方可以直接求出來(lái)：然后可以輕易得到通項(xiàng)公式，上邊已經(jīng)給出，這里不再贅述。（3）特征方程解法通過(guò)方法（2），我們可以推導(dǎo)出一般的線性遞推數(shù)列的通項(xiàng)求解方法，也就是特征方程法。我們可以發(fā)現(xiàn)，對(duì)于這種數(shù)列，通項(xiàng)總是可以表示為的形式，因此可以直接利用已知項(xiàng)求解，。具體做法如下：a.由遞推數(shù)列構(gòu)造特征方程，解出兩個(gè)特征值。b.帶入,列出如下方程：解得這樣直接寫(xiě)出通項(xiàng)公式，是比較簡(jiǎn)單的做法。（4）母函數(shù)法（此方法涉及組合數(shù)學(xué)知識(shí)）設(shè)斐波那契數(shù)列的母函數(shù)為,即解得再由冪級(jí)數(shù)展開(kāi)公式……合并同類項(xiàng)并與的系數(shù)比較即可。到這里，求解斐波那契數(shù)列通項(xiàng)的方法就說(shuō)的差不多了。無(wú)論是計(jì)算機(jī)求解還是數(shù)學(xué)推導(dǎo)，都體現(xiàn)出了非常多的技巧。而斐波那契數(shù)列的許多特性，就更加有意思了。三、斐波那契數(shù)列的數(shù)學(xué)性質(zhì)1.與黃金比的關(guān)系由通項(xiàng)公式，求相鄰兩項(xiàng)的商的極限，結(jié)果是黃金比，所以斐波那契數(shù)列又稱為黃金比數(shù)列。斐波那契數(shù)列和黃金比還和一個(gè)有趣的數(shù)學(xué)概念——連分?jǐn)?shù)有關(guān)：2.一些簡(jiǎn)單的規(guī)律（1）任意連續(xù)四個(gè)斐波那契數(shù)，可以構(gòu)造出一個(gè)畢達(dá)哥拉斯三元組。如取1,1,2,3.中間兩數(shù)相乘再乘2==》4外層2數(shù)乘積==》3中間兩數(shù)平方和==》5得到3,4,5.下一組是5,12,13,，有興趣的讀者可以再試著推一推，證明也是容易的。（2）整除性每3個(gè)連續(xù)的斐波那契數(shù)有且只有一個(gè)被2整除，每4個(gè)連續(xù)的斐波那契數(shù)有且只有一個(gè)被3整除，每5個(gè)連續(xù)的斐波那契數(shù)有且只有一個(gè)被5整除，每6個(gè)連續(xù)的斐波那契數(shù)有且只有一個(gè)被8整除，每7個(gè)連續(xù)的斐波那契數(shù)有且只有一個(gè)被13整除，…………每n個(gè)連續(xù)的斐波那契數(shù)有且只有一個(gè)被整除.（3）一些恒等式3.楊輝三角中的斐波那契數(shù)列如圖所示，每條斜線上的數(shù)的和就構(gòu)成斐波那契數(shù)列。

即有4.相關(guān)數(shù)列：盧卡斯（Lucas）數(shù)列盧卡斯數(shù)列的定義除了第0項(xiàng)為2之外，與斐波那契數(shù)列完全一致。即其通項(xiàng)公式為：盧卡斯數(shù)列和斐波那契數(shù)列有這些關(guān)系：5.組合數(shù)學(xué)（1）一些恒等式（2）同余特性當(dāng)p為大于5的素?cái)?shù)時(shí)，有：其中斐波那契數(shù)列還有許許多多的性質(zhì)，我就不再一一介紹了。跑題了這么久，終于開(kāi)始要真正回答問(wèn)題了：斐波那契數(shù)列有什么用？四、斐波那契數(shù)列的應(yīng)用1.算法a.斐波那契堆斐波那契堆(Fibonacciheap)是計(jì)算機(jī)科學(xué)中最小堆有序樹(shù)的集合。它和二項(xiàng)式堆有類似的性質(zhì)，可用于實(shí)現(xiàn)合并優(yōu)先隊(duì)列。特點(diǎn)是不涉及刪除元素的操作有O(1)的平攤時(shí)間，用途包括稠密圖每次Decrease－key只要O(1)的平攤時(shí)間，和二項(xiàng)堆的O(lgn)相比是巨大的改進(jìn)。斐波那契堆由一組最小堆構(gòu)成，這些最小堆是有根的無(wú)序樹(shù)?？梢赃M(jìn)行插入、查找、合并和刪除等操作1）插入：創(chuàng)建一個(gè)僅包含一個(gè)節(jié)點(diǎn)的新的斐波納契堆，然后執(zhí)行堆合并2）查找：由于用一個(gè)指針指向了具有最小值的根節(jié)點(diǎn)，因此查找最小的節(jié)點(diǎn)是平凡的操作。3）合并：簡(jiǎn)單合并兩個(gè)斐波納契堆的根表。即把兩個(gè)斐波納契堆的所有樹(shù)的根首尾銜接并置。4）刪除（釋放）最小節(jié)點(diǎn)分為三步：查找最小的根節(jié)點(diǎn)并刪除它，其所有的子節(jié)點(diǎn)都加入堆的根表，即它的子樹(shù)都成為堆所包含的樹(shù)；需要查找并維護(hù)堆的最小根節(jié)點(diǎn)，但這耗時(shí)較大。為此，同時(shí)完成堆的維護(hù)：對(duì)堆當(dāng)前包含的樹(shù)的度數(shù)從低到高，迭代執(zhí)行具有相同度數(shù)的樹(shù)的合并并實(shí)現(xiàn)最小樹(shù)化調(diào)整，使得堆包含的樹(shù)具有不同的度數(shù)。這一步使用一個(gè)數(shù)組，數(shù)組下標(biāo)為根節(jié)點(diǎn)的度數(shù)，數(shù)組的值為指向該根節(jié)點(diǎn)指針。如果發(fā)現(xiàn)具有相同度數(shù)的其他根節(jié)點(diǎn)則合并兩棵樹(shù)并維護(hù)該數(shù)組的狀態(tài)。對(duì)當(dāng)前堆的所有根節(jié)點(diǎn)查找最小的根節(jié)點(diǎn)。5）降低一個(gè)點(diǎn)的鍵值：對(duì)一個(gè)節(jié)點(diǎn)的鍵值降低后，自鍵值降低的節(jié)點(diǎn)開(kāi)始自下而上的迭代執(zhí)行下述操作，直至到根節(jié)點(diǎn)或一個(gè)未被標(biāo)記（marked）節(jié)點(diǎn)為止：如果當(dāng)前節(jié)點(diǎn)鍵值小于其父節(jié)點(diǎn)的鍵值，則把該節(jié)點(diǎn)及其子樹(shù)摘下來(lái)作為堆的新樹(shù)的根節(jié)點(diǎn)；其原父節(jié)點(diǎn)如果是被標(biāo)記（marked）節(jié)點(diǎn)，則也被摘下來(lái)作為堆的新樹(shù)的根節(jié)點(diǎn)；如果其原父節(jié)點(diǎn)不是被標(biāo)記（marked）節(jié)點(diǎn)且不是根節(jié)點(diǎn)，則其原父節(jié)點(diǎn)被加標(biāo)記。如果堆的新樹(shù)的根節(jié)點(diǎn)被標(biāo)記（marked），則去除該標(biāo)記。6）刪除節(jié)點(diǎn)：把被刪除節(jié)點(diǎn)的鍵值調(diào)整為負(fù)無(wú)窮小，然后執(zhí)行“降低一個(gè)節(jié)點(diǎn)的鍵值”算法，然后再執(zhí)行“刪除最小節(jié)點(diǎn)”算法。斐波那契堆b.歐幾里得算法的時(shí)間復(fù)雜度歐幾里得算法是求解兩個(gè)正整數(shù)最大公約數(shù)的算法，又稱輾轉(zhuǎn)相除法。代碼如下：intgcd(inta,intb){returnb?gcd(b,a%b):a;}在最壞的情況下，我們可以證明，若a較小，需要計(jì)算的次數(shù)為n，則.雖然說(shuō)一般分析的時(shí)候會(huì)當(dāng)成對(duì)數(shù)階，但數(shù)論最常用的歐幾里得算法竟然與斐波那契數(shù)列有關(guān)，也確實(shí)是很讓人吃驚呢。2.物理學(xué)：氫原子能級(jí)問(wèn)題假定我們現(xiàn)在有一些氫氣原子，一個(gè)電子最初所處的位置是最低的能級(jí)（Groundleverofenergy），屬于穩(wěn)定狀態(tài)。它能獲得一個(gè)能量子或二個(gè)能量子（Quantaofenergy）而使它上升到第一能級(jí)或者第二能級(jí)。但是在第一級(jí)的電子如失掉一個(gè)能量子就會(huì)下降到最低能級(jí)，它如獲得一個(gè)能量子就會(huì)上升到第二級(jí)來(lái)?，F(xiàn)在研究氣體吸收和放出能量的情形，假定最初電子是處在穩(wěn)定狀態(tài)即零能級(jí)，然后讓它吸收能量，這電子可以跳到第1能級(jí)或第2能級(jí)。然后再讓這氣體放射能量，這時(shí)電子在1級(jí)能級(jí)的就要下降到0能級(jí)，而在第2能級(jí)的可能下降到0能級(jí)或者第1能級(jí)的位置去。電子所處的狀態(tài)可能的情形是：1、2、3、5、8、13、21…種。這是斐波那契數(shù)列的一部份。3.自然界：植物的生長(zhǎng)科學(xué)家發(fā)現(xiàn)，一些植物的花瓣、萼片、果實(shí)的數(shù)目以及排列的方式上，都有一個(gè)神奇的規(guī)律，它們都非常符合著名的斐波那契數(shù)列。例如：薊，它們的頭部幾乎呈球狀。在下圖中，你可以看到兩條不同方向的螺旋。我們可以數(shù)一下，順時(shí)針旋轉(zhuǎn)的（和左邊那條旋轉(zhuǎn)方向相同）螺旋一共有13條，而逆時(shí)針旋轉(zhuǎn)的則有21條。此外還有菊花、向日葵、松果、菠蘿等都是按這種方式生長(zhǎng)的。還有菠蘿、松子等，也都符合這個(gè)特點(diǎn)，一般會(huì)出現(xiàn)34,55，89和144這幾個(gè)數(shù)字。

最后上一張“斐波那契樹(shù)”的圖片：是的，這玩意就長(zhǎng)這樣，這種植物是存在的。4.波浪理論與股市這個(gè)答主不懂，大家可自行閱讀文章波浪理論斐波那契數(shù)列與黃金分割率。不過(guò)波浪的形狀確實(shí)符合下邊要說(shuō)的斐波那契螺旋：5.斐波那契螺旋斐波那契螺旋又稱黃金螺旋，在自然界中廣泛存在。如圖是一個(gè)邊長(zhǎng)為斐波那契數(shù)列的正方形組成的矩形。（加一句：看著這個(gè)圖，是不是能發(fā)現(xiàn)是顯而易見(jiàn)的？）這樣連起來(lái)就是斐波那契螺旋了貝殼螺旋輪廓線向日葵的生長(zhǎng)神奇的花6.建筑學(xué)7.據(jù)說(shuō)一個(gè)小男孩參考斐波那契數(shù)列發(fā)明了太陽(yáng)能電池樹(shù)：一名13歲的男孩根據(jù)斐波那契數(shù)列發(fā)明了太陽(yáng)能電池樹(shù)，其產(chǎn)生的電力比太陽(yáng)能光伏電池陣列多20-50%。斐波那契數(shù)列類似從0和1開(kāi)始，之后的數(shù)是之前兩數(shù)的和，如0，1，1，2，3，5，8，13，21...AidanDwye在觀察樹(shù)枝分叉時(shí)發(fā)現(xiàn)它的分布模式類似斐波那契數(shù)列，這是大自然演化的一種結(jié)果，可能有助于樹(shù)葉進(jìn)行光合作用。因此，Dwye猜想為什么不按照斐波那契數(shù)列排列太陽(yáng)能電池？他設(shè)計(jì)了太陽(yáng)能電池樹(shù)，發(fā)現(xiàn)它的輸出電力提高了20%，每天接受光照的時(shí)間延長(zhǎng)了2.5小時(shí)。8.斐波那契螺旋形的搖椅媽媽搖椅是設(shè)計(jì)師PatrickMessier為自己的妻子兼合作伙伴SophieFournier設(shè)計(jì)的，當(dāng)時(shí)他們剛有了第一個(gè)寶寶。當(dāng)Sophie宣布自己懷孕時(shí)，她說(shuō)想要一把搖椅，但發(fā)現(xiàn)沒(méi)有一把搖椅能滿足美觀舒適的標(biāo)準(zhǔn)，于是Patrick決定自己做一把。于是就有了這把媽媽搖椅。像是一個(gè)飄在空中的絲帶，由一片纖維玻璃做成，曲線服從\o"服從斐波那契數(shù)列分布的俄羅斯套娃刀具"斐波那契數(shù)列分布，經(jīng)過(guò)特殊的高光聚氨酯處理。五、數(shù)學(xué)上的擴(kuò)展（1）廣義斐波那契數(shù)列定義：,數(shù)列滿足：其通項(xiàng)為：當(dāng)時(shí)即為斐波那契數(shù)列。（2）反斐波那契數(shù)列定義：反斐波那契數(shù)列相鄰項(xiàng)比值的極限為。（3）巴都萬(wàn)數(shù)列(A000931-OEIS)斐波那契數(shù)列可以刻畫(huà)矩形，而巴都萬(wàn)數(shù)列則刻畫(huà)的是三角形。其定義如下：(4)未解之謎：角谷猜想對(duì)一個(gè)正整數(shù)，若為奇數(shù)則乘3加1，若為奇數(shù)則除以2，通過(guò)有限次這樣的操作，能否使得該數(shù)變成1？這個(gè)猜想和斐波那契數(shù)列又很大關(guān)系，具體的可以看角谷猜想的斐波那契數(shù)列現(xiàn)象。六、總結(jié)斐波那契數(shù)列是各個(gè)學(xué)科中都出現(xiàn)的小滑頭，它許多漂亮的性質(zhì)讓我們著迷。上文我所描述的這些只是它的冰山一角，權(quán)當(dāng)拋磚引玉。大家讀完了我的答案，還可以再結(jié)合自己的專業(yè)去看一些相關(guān)的資料，更好的去了解這個(gè)有趣的數(shù)列。七、參考文獻(xiàn)[1]/xsjl/szh/lec5.pdf[2]斐波那契數(shù)列_一米陽(yáng)光[3]斐波那契數(shù)列的規(guī)律性[4]HYPERLINK"/a