問題 22 斐波那契數(shù)列

問題：斐波那契數(shù)列（Fibonacci sequence），又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱“兔子數(shù)列”，其數(shù)值為：1、1、2、3、5、8、13、21、34……在數(shù)學(xué)上，這一數(shù)列以如下遞推的方法定義：F(0)=1，F(xiàn)(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）【摘自百度百科】

?

斐波那契數(shù)列現(xiàn)在還有名，一是它本身有許多特別的數(shù)學(xué)性質(zhì)，至今很多數(shù)學(xué)競賽還可以以此出新題；二是科學(xué)家發(fā)現(xiàn)很多實(shí)際的結(jié)構(gòu)的數(shù)學(xué)表述都與斐波那契數(shù)列有關(guān)，比如黃金分割系數(shù)。

?

求解斐波那契數(shù)幾個層次

?

層次一，從遞歸算法開始的不斷優(yōu)化，直至設(shè)計出線性復(fù)雜度的迭代算法。

斐波那契數(shù)列是一個經(jīng)典的遞推公式，F(xiàn)(n)=F(n - 1)+F(n - 2)（數(shù)學(xué)知識），利用這個遞推公式（算法邏輯），就可以求第n個斐波那契數(shù)。

利用遞推公式，寫一個遞歸算法（程序與數(shù)據(jù)結(jié)構(gòu)），是最直接的（為什么，這需要去學(xué)習(xí) 遞歸算法；其實(shí)每本講述遞歸的教材，都會用斐波那契數(shù)列舉例）。

而且，這個算法，還可以優(yōu)化，這也是講述算法優(yōu)化的教材，都會用求解斐波那契數(shù)列算法優(yōu)化舉例，直至設(shè)計出線性復(fù)雜度的迭代算法。

?

層次二，計算機(jī)實(shí)際運(yùn)行上述算法設(shè)計的程序時，會因?yàn)橛布s束，出現(xiàn)結(jié)果“溢出”現(xiàn)象。也就是斐波那契數(shù)的數(shù)值，超過了計算機(jī)存儲空間能表示的整數(shù)的最大允許范圍。（這是一個數(shù)學(xué)，算法，和程序，三者之間的一個很有意思的認(rèn)知，也是一個具有計算思維的IT人應(yīng)該知道的元認(rèn)知）

?

層次三，不用遞推，直接用以n為變量顯示地定義（計算）第n個斐波那契數(shù)的代數(shù)表達(dá)式，即斐波那契數(shù)通項(xiàng)公式（數(shù)學(xué)知識）就可以突破溢出問題（當(dāng)然，也可以利用數(shù)組模擬加法長式計算來實(shí)現(xiàn)不受硬件環(huán)境影響的斐波那契數(shù)算法）

?

【作者感受】

斐波那契數(shù)列基本是每本程序設(shè)計語言，數(shù)據(jù)結(jié)構(gòu)或算法教材必有的例題，因?yàn)樗鼇碓匆粋€數(shù)學(xué)公式（公式不復(fù)雜，沒有學(xué)習(xí)難度，關(guān)鍵是還有現(xiàn)實(shí)實(shí)用價值，可以說是完美的例題來源），求解斐波那契數(shù)列的算法，可以不斷優(yōu)化，這對初學(xué)者感受“算法之美”是很有沖擊力的。

求解斐波那契數(shù)列的程序可以從遞歸優(yōu)化到迭代，還涉及計算機(jī)表示的變量的“溢出”這一計算機(jī)運(yùn)行的獨(dú)特現(xiàn)象。

簡單說，斐波那契數(shù)列，教材喜歡用，教師喜歡用，初學(xué)者也喜歡學(xué)，而且這個看起來簡單的東西，其實(shí)深究起來，對編程高手都有不斷品味的價值。