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

牟曉東

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

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

一般而言，兔子在出生兩個月之后就會有繁殖能力，一對兔子每月能生出一對小兔子。假設兔子不死亡，一年之后會繁殖出多少對兔子？經(jīng)分析后不難發(fā)現(xiàn)，成年兔子的對數(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編程來求解這個數(shù)列。

2.遞歸解法

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

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

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

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

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

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

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