Python編程求解斐波那契數列

牟曉東

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

1.斐波那契數列的數學解析

一般而言，兔子在出生兩個月之后就會有繁殖能力，一對兔子每月能生出一對小兔子。假設兔子不死亡，一年之后會繁殖出多少對兔子？經分析后不難發現，成年兔子的對數符合這樣的函數定義：

F（0）=0，F（1）=1，F（n）=F（n-1）+F（n-2）（n≥2，n∈N自然數）

那么下面我們使用Python編程來求解這個數列。

2.遞歸解法

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

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

3.Python優化解法

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

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

4.求任意項斐波那契數列

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