Python編程求解斐波那契數(shù)列

牟曉東

斐波那契（Fibonacci）數(shù)列又稱“黃金分割數(shù)列”，最早是由意大利數(shù)學(xué)家Fibonacci以兔子繁殖為例引入，因此又稱“兔子數(shù)列”。這個(gè)數(shù)列的第0項(xiàng)是0，第1項(xiàng)是1，從第3項(xiàng)開(kāi)始，每一項(xiàng)均等于前兩項(xiàng)之和，即：0，1，1，2，3，5，8，13，21……

1.斐波那契數(shù)列的數(shù)學(xué)解析

一般而言，兔子在出生兩個(gè)月之后就會(huì)有繁殖能力，一對(duì)兔子每月能生出一對(duì)小兔子。假設(shè)兔子不死亡，一年之后會(huì)繁殖出多少對(duì)兔子？經(jīng)分析后不難發(fā)現(xiàn)，成年兔子的對(duì)數(shù)符合這樣的函數(shù)定義：

F（0）=0，F(xiàn)（1）=1，F(xiàn)（n）=F（n-1）+F（n-2）（n≥2，n∈N自然數(shù)）

那么下面我們使用Python編程來(lái)求解這個(gè)數(shù)列。

2.遞歸解法

遞歸是求解這種數(shù)列的常規(guī)方法。遞歸即函數(shù)在運(yùn)行過(guò)程中不斷地直接或間接調(diào)用自身的一種算法，比如在Python中通過(guò)“def fib1（n）：”來(lái)定義fib1（）函數(shù)，其主體內(nèi)容為“三分支”結(jié)構(gòu)：前兩種（if和elif）通過(guò)判斷參數(shù)n是0還是1來(lái)分別對(duì)應(yīng)這個(gè)數(shù)列的前兩項(xiàng)0和1，二者均通過(guò)return語(yǔ)句來(lái)返回對(duì)應(yīng)的數(shù)值。注意判斷條件中的雙等號(hào)的含義是“等于”，一個(gè)等號(hào)是“賦值”運(yùn)算。第三個(gè)分支（else）是“return fib1（n-1）+fib1（n-2）”，意思是遞歸運(yùn)算返回該項(xiàng)前兩項(xiàng)值的和：F（n）=F（n-1）+F（n-2）。

最后使用“print（‘一年之后會(huì)繁殖出的兔子對(duì)數(shù)為：，fib1（12））”來(lái)輸出運(yùn)算結(jié)果，其中的“fib（12）”作用是調(diào)用fib1（）函數(shù)，參數(shù)為12（一年的月數(shù)）。保存程序?yàn)閒ibonacci1.py，運(yùn)行后得到結(jié)果是144（如圖1）。

3.Python優(yōu)化解法

Python支持多變量在一行語(yǔ)句中同時(shí)賦值的運(yùn)算，比如“x，y=y，x”，意思是x和y這兩個(gè)變量的值進(jìn)行“互換”。對(duì)于這種兩個(gè)變量進(jìn)行值互換的運(yùn)算，其他編程語(yǔ)言幾乎都是通過(guò)第三方變量來(lái)“暫存”中間數(shù)據(jù)的方式來(lái)完成的，例如最初有“x=3”和“y=4”兩個(gè)賦值語(yǔ)句，分別將3和4這兩個(gè)數(shù)據(jù)給變量x和y;接著需要再通過(guò)三個(gè)賦值語(yǔ)句完成x和y數(shù)據(jù)的互換：“z=x”、“x=y”和“y=z”，意思分別是“將x的值（3）給z”、“將y的值（4）給x”和“將z的值（3）給y”，此時(shí)x的值變成4、y的值變成3。

如果使用Python的多變量同時(shí)賦值方法來(lái)編程，就可以通過(guò)“def fib2（n）：”來(lái)定義fib2（）函數(shù)。首先通過(guò)“a，b = 0，1”語(yǔ)句，實(shí)現(xiàn)變量a和b同時(shí)被分別賦值0和1，對(duì)應(yīng)斐波那契數(shù)列的前兩項(xiàng);接著使用for循環(huán)和range（）函數(shù)“for i in range（n）：”，其循環(huán)體為“a，b = b，a+b”，意思是將b的值給a、將a+b的值給b，實(shí)現(xiàn)之前使用遞歸算法完成的第三項(xiàng)及之后項(xiàng)的斐波那契數(shù)列運(yùn)算;for循環(huán)體結(jié)束后，通過(guò)“return a”語(yǔ)句將變量a的值返回;最后仍是通過(guò)print語(yǔ)句的“fib2（12）”來(lái)調(diào)用函數(shù)計(jì)算并輸出，保存程序?yàn)閒ibonacci2.py，運(yùn)行結(jié)果仍是144（如圖2）。

4.求任意項(xiàng)斐波那契數(shù)列

理論上講，斐波那契數(shù)列的值是無(wú)窮的，如何使用Python編程來(lái)實(shí)現(xiàn)輸出數(shù)列的任意項(xiàng)呢？可以先通過(guò)input函數(shù)來(lái)接收用戶從鍵盤上輸入的“要求”，注意一定要使用int（）函數(shù)將該字符串型數(shù)據(jù)轉(zhuǎn)換為整數(shù)型數(shù)據(jù);接著定義fib3（）函數(shù)，內(nèi)容與上面的fib2（）完全相同，同樣是返回a的值;然后使用print語(yǔ)句輸出提示信息，再同樣是通過(guò)for循環(huán)加range（）函數(shù)，循環(huán)體內(nèi)的“print（fib3（i），end=‘ ）”是調(diào)用fib3（）函數(shù)，其中的“end=‘ ”作用是控制打印輸出的各項(xiàng)Fibonacci數(shù)列值之間使用一個(gè)空格來(lái)分隔（默認(rèn)是回車）。將程序保存為fibonacci3.py，運(yùn)行測(cè)試，分別嘗試輸入10、20和50，程序就會(huì)根據(jù)要求輸出斐波那契數(shù)列的前10、20和50個(gè)數(shù)值（如圖3），大家不妨一試。