費波那契數列 ( 費氏數列 )

費波那契數列又稱之為費氏數列、黃金分割數列，這篇教學將會介紹使用 Python 函式的遞迴特性，做出一個費波那契數列。

本篇使用的 Python 版本為 3.7.12，所有範例可使用 Google Colab 實作，不用安裝任何軟體 ( 參考：使用 Google Colab )

什麼是費波那契數列？

費波那契數列是一位義大利人費波那契 Leonardo Fibonacci，為了描述兔子生長的數目，使用這個數列來表現，費氏數列從 0 和 1 開始，之後的數字就是由之前的兩數相加而得出，下方列出費氏數列開始的一些數字 ( 更多請參考：費波那契數 )。

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377 ,610, 987……

費氏數值為數列中前後兩個數值的加總，數列中的前後數值比例約為 1.618…，也就是所謂的黃金比例。

運用遞迴產生費波那契數列

下方的程式碼，使用遞迴的方式來建立費波那契數列。

參考：遞迴、重複迴圈 ( for、while )

def fib(n): # 建立函式 fib，帶有參數 n

if n > 1: # 如果 n 大於 1

return fib(n-1) + fib(n-2) # 使用遞迴

return n

for i in range(20): # 產生 20 個數字

print(fib(i), end = ',') # 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181

如果無法理解當中遞迴的原理，可以參考下圖：

使用迴圈產生費波那契數列

下方的例子，也可以在完全不使用遞迴的狀況下，單純透過「迴圈」+「串列」來呈現費波那契數列。

參考：for 迴圈、刪除串列項目、增加串列項目

n = int(input()) # 輸入要產生的數字數量

arr = [] # 建立一個空串列，記錄數字

for i in range(n): # 使用 for 迴圈，重複指定的數字

if i==0: # 如果 i 等於 0，a 為 0

a = 0

elif i==1: # 如果 i 等於 1，a 為 1

a = 1

arr = [0, 1] # 將串列設定為 [0, 1]

else: # 如果 i 大於 1

a = arr[0] + arr[1] # a 等於串列的兩個數字相加

del arr[0] # 刪除串列的第一個項目

arr.append(a) # 將 a 加入串列成為第二個項目

print(a, end=',') # 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181

意見回饋

如果有任何建議或問題，可傳送「意見表單」給我，謝謝～