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

費波那契數列又稱之為費氏數列、黃金分割數列，這篇教學將會介紹使用 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

意見回饋

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