孔乙己自己知道不能和他們談天，便只好向 Intern 說話。有一回對我說道，「你寫過程式碼麽？」我略略點一點頭。他說，「寫過程式碼，……我便考你一考。費氏數列的輸出，怎樣實作？」我想，討飯一樣的人，也配考我麽？便回過臉去，不再理會。孔乙己等了許久，很懇切的說道，「不能寫罷？……我教給你，記著！這些程式碼應該記著。將來做 Leader 的時候，開發計畫要用。」我暗想我和 Leader 的等級還很遠呢，而且我們 Leader 也從不在計畫裏寫斐波那契；又好笑，又不耐煩，懶懶的答他道，「誰要你教，不是遞迴麽？」孔乙己顯出極高興的樣子，將兩個指頭的長指甲敲著鍵盤，點頭說，「對呀對呀！……斐波那契有四樣寫法，你知道麽？」我愈不耐煩了，努著嘴走遠。孔乙己剛在命令列開啟 Vim，想在裏面寫程式碼，見我毫不熱心，便又嘆一口氣，顯出極惋惜的樣子。
（改編自 魯迅【孔乙己】）
「面試八股」是每個程式設計師找工作時都繞不開的坎，今天我們就來看看，如何寫一個輸出費氏數列的程式碼吧。
先說下，什麽是
費氏數列
？
斐波那契（Fibonacci）數列，又稱黃金分割數列，因數學家列昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為「兔子數列」，指的是這樣一個數列：
1、1、2、3、5、8、13、21、34……
在數學上，費氏數列以如下被以遞推的方法定義：
F(1) = 1
F(2) = 1
F(n) = F(n - 1) + F(n - 2) （n ≥ 3，n ∈ N*）
簡單來講就是：數列中 某一項的值，等於它的前一項加上前前一項的和 。
在現代物理、準晶體結構、化學等領域，斐波納契數列都有直接的套用，為此，美國數學會從 1963 年起出版了以【斐波納契數列季刊】為名的一份數學雜誌，用於專門刊載這方面的研究成果。（摘自 百度百科）
我曾經也把手寫斐波那契作為面試題之一。
1. 遞迴
在編程教程中提到費氏數列，通常都是用來講解遞迴函式。當一個關於 N 的問題可以轉換為關於 N - k 的同樣問題時，它就可以嘗試用遞迴的思路來解決。
def fib_1(n): if n <= 1: return 1 return fib_1(n-1) + fib_1(n-2)for i in range(20): print(fib_1(i), end=' ')
2. 迴圈
但斐波那契並非一定要用遞迴實作。事實上，所有的遞迴都可以用迴圈來實作。
def fib_2(n): a, b = 0, 1 for i in range(n): print(b, end=' ') a, b = b, a + bfib_2(20)
3. 生成器
用生成器的思路本質來說和上面的迴圈是一樣的，只是實作的時候用了 yield 。
def fib_3(n): a, b = 0, 1 while n > 0: yield b a, b = b, a + b n -= 1for i in fib_3(20): print(i, end=' ')
4. 矩陣相乘
此方法的原理是利用二階矩陣的相乘：
import numpy as npdef fib_4(n): for i in range(n): res = pow(np.matrix([[1, 1], [1, 0]], dtype='int64'), i) * np.matrix([[1], [0]]) print(int(res[0][0]), end=' ')fib_4(20)
上述 4 種方法的輸出結果都是：
1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
費氏數列的實作方法並不僅這 4 種。如果你有其他的實作，歡迎在留言中補充。
作者：Crossin的編程教室
Crossin的新書【 碼上行動：用ChatGPT學會Python編程 】已經上市了。 本書以ChatGPT為輔助，系統全面地講解了如何掌握Python編程，適合Python零基礎入門的讀者學習。
購買後可加入讀者交流群，Crossin為你開啟陪讀模式，解答你在閱讀本書時的一切疑問。
添加微信 crossin123 ，加入編程教室共同學習 ~
感謝 轉發 和 點贊 的各位~
