© Sashkin/Shutterstock.com
斐波那契數列無疑是有史以來最著名的數學數列之一。幾個世紀以來，數學家和科學家一直在數學和科學領域使用這個數列，並以中世紀著名的意大利數學家斐波那契命名。
斐波那契數列是一系列數字，其中每個後續數字都是前兩個數字的總和，從 0 和 1 開始。該序列通常用 Fn 表示，如下所示:0, 1, 1、2、3、5、8、13、21、34、55、89、144、233 等。
但是有什麼大不了的?我們為什麼要關心斐波那契數列?好吧，事實證明這個序列不僅僅是一些任意的數字序列。
斐波那契數列遍布自然界和許多科學領域，它在計算機科學和編程方面有著重要的應用。該系列在計算機科學中的意義源於可以生成其數字的各種算法。
Python 等編程語言具有生成斐波那契數列的內置函數。如果您有興趣了解這些函數背後的算法，請堅持下去，因為本文將解釋用於生成斐波那契數列的 7 種主要算法和方法。
為斐波那契數列創建程序的不同方法
存在多種生成斐波那契數列的方法/途徑，每種都有不同的時間和空間複雜性。找到第 n 個 Fibonacci 數的最直接的方法是使用遞歸。
但是，這種方法效率不高，會導致大量冗餘計算。因此，我們將與其他方法一起探索遞歸，看看哪些方法最有效。
遞歸
遞歸是一種解決問題的方法，其中解決方案取決於對同一問題的較小實例的解決方案。在斐波那契數列的上下文中，遞歸解決方案的工作原理是將尋找第 n 個斐波那契數的問題分解為兩個較小的問題:尋找第 (n-1) 個斐波那契數和尋找第 (n-2) 個斐波那契數。
此過程遞歸地繼續，直到到達基本情況，其中 n 為 0 或 1。基本情況表示函數必須滿足以停止調用自身的條件。一旦滿足，該函數就簡單地返回 n。對於 n 的所有其他值，該函數遞歸地調用自身，將 n-1 和 n-2 作為參數/參數傳入。
以下示例顯示了一個簡單的 Python 程序，該程序實現遞歸以生成斐波那契數:
def fibonacci(n):
if n=1: # base case
返回 n
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7)) # 輸出:13
函數首先檢查基本情況它返回 n。如果 n 大於 1，該函數以 n-1 和 n-2 作為參數遞歸調用自身，並將它們的返回值相加。這是因為斐波那契數列中的第 n 個數等於數列中第 (n-1) 和第 (n-2) 個數之和。
遞歸調用繼續直到達到基本情況並且函數返回序列中的第 n 個數字。我們可以獲得遞歸解決方案的時間複雜度——它的指數級為 O(2n)，因為函數會為每個 n 值調用自身兩次。
隨著 n 變大，這種方法很快就會變得低效，使得這種方法對於較大的 n 值不切實際。空間複雜度為O(n)，是線性的，因為遞歸樹的最大深度為n。
迭代
迭代是求解斐波那契數列的一種更有效的方法問題。迭代方法涉及通過重複執行一組指令直到滿足特定條件來解決問題。
在斐波那契數列的上下文中，迭代解決方案通過從前兩個斐波那契數開始併計算使用前兩個的下一個斐波那契數。這個過程一直持續到計算出第 n 個斐波那契數。
斐波那契數列最早出現在拉丁手稿“Liber Abaci”（1202 年）中，用於計算兔子數量的增長。
©TippaPatt/Shutterstock.com
我們可以通過以下方式使用迭代來創建斐波那契數列的簡單程序:
def fibonacci(n):
如果 n==0:
返回 0
elif n==1:
返回 1
其他:
fib1, fib2=0, 1
for i in range(2, n+1):
fib=fib1 + fib2
fib1, fib2=fib2, fib
return fib2
在這裡，我們使用循環在線性時間內計算第 n 個斐波那契數。我們通過從序列中的前兩個數字（0 和 1）開始並迭代計算下一個數字作為前兩個數字的總和來實現這一點。
我們在變量中跟踪前兩個數字，並在每次迭代時更新它們。經過n次迭代後，我們返回第n個數。
迭代求解的時間複雜度為O(n)，是線性的。這是因為 for 循環運行 n-1 次以計算第 n 個斐波那契數。由於該函數僅使用常數個變量來計算第 n 個斐波那契數，因此其空間複雜度為 O(1)，這是常數。
Memoization
Memoization 是一種方法通過存儲昂貴的函數調用的結果並在再次出現相同的輸入時返回緩存的結果來解決問題。
在斐波那契數列的上下文中，記憶解決方案通過存儲子問題的解決方案並返回緩存結果（如果可用）來工作。
通過這種方式，程序計算解決方案對每個子問題僅執行一次，並在需要時重用它。
這是實現記憶的示例:
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
elif n=1:
返回 n
else:
memo[n]=fibonacci(n-1, memo) + fibonacci(n-2, memo)
return memo[n]
此示例使用頂部-down 方法通過緩存先前計算的值來計算第 n 個斐波那契數，以避免冗餘計算。該函數首先檢查它是否已經計算並緩存了 Python 字典中的第 n 個斐波那契數的值。如果有，它返回緩存的值。
如果還沒有，它遞歸地計算值作為第 (n-1) 個和第 (n-2) 個斐波那契數的總和，將計算值緩存在字典中，並且返回它。
memoization 解決方案的時間複雜度是 O(n)，它是線性的。這是因為該程序只計算每個斐波那契數一次並將其存儲在備忘錄字典中以備將來使用。空間複雜度也是O(n)，是線性的，因為memo字典存儲了最多n個子問題的解。
動態規劃
動態規劃是一種解決一個問題的方法通過將問題分解為更小的子問題並存儲這些子問題的解決方案來避免冗餘計算。
在斐波那契數列的上下文中，動態規劃解決方案通過以自下而上的方式計算斐波那契數並將解決方案存儲在數組中來工作。這樣，每個子問題的解只計算一次並在需要時重複使用。
考慮以下示例:
def fibonacci(n):
fib=[0, 1]
for i in range(2, n+1):
fib.append(fib[i-1] + fib[i-2])
return fib[n]
該函數使用 Python 列表來存儲序列的計算值，從前兩個值開始。然後，它從 2 迭代到 n，將第 i 個值計算為第 (i-1) 個和第 (i-2) 個值的總和，並將其存儲在列表中。最後返回列表中的第n個值。
動態規劃求解的時間複雜度為O(n)，是線性的。該算法的時間複雜度為 O(n)，因為 for 循環通過運行 n-1 次來計算第 n 個斐波那契數，並且每次計算都需要常數時間。
此外，該算法的空間複雜度為 O(n)，因為它使用大小為 n 的列表來存儲子問題的解。
矩陣求冪
矩陣求冪是一種通過提高矩陣的冪來解決問題的方法。在斐波那契數列的上下文中，矩陣求冪解決方案通過使用具有斐波那契數的矩陣對其進行 n-1 次方以獲得第 n 個斐波那契數。
e 可以使用矩陣求冪來為斐波那契數列創建一個 Python 程序，如下所示:
import numpy as np
def fibonacci(n):
F=np.array([[ 1, 1], [1, 0]])
return np.linalg.matrix_power(F, n-1)[0, 0]
在這個例子中，我們’我們重新使用矩陣求冪技術以對數時間計算第 n 個斐波那契數。為此，我們將 2×2 矩陣提高到 n-1 次方，並將其與初始狀態向量 [0, 1] 相乘。得到的矩陣包含第 n 個和第 (n+1) 個斐波那契數，我們返回第 n 個數。
矩陣求冪解的時間複雜度為 O(log n)，這當然是對數的。矩陣乘法中使用的分而治之算法減少了所需的乘法次數。因此，空間複雜度為 O(1)，它是常數，因為只使用了常數量的內存。
Binet 公式
Binet 公式是計算第 n 個斐波那契數，而無需計算所有先前的斐波那契數。
公式常寫為:Fn=round((Φ^n – (1-Φ)^n)/√5)，其中Φ(phi)為黃金比例。
比奈的公式表明隨著 n 的增加，兩個連續的斐波那契數的比率趨向於黃金比率。
©TippaPatt/Shutterstock.com
在斐波那契數列的背景下，比奈的公式通過使用黃金比率來計算，它是 (1 + √5)/2，它的共軛是 1 – √5)/2。
Python 中的一個例子是:
def fibonacci(n):
golden_ratio=(1 + 5**0.5)/2
返回回合((golden_ratio**n – (1 – golden_ratio)**n)/5**0.5 )
函數首先定義了黃金比例。接下來，我們使用 Binet 公式計算第 n 項，並返回結果的四捨五入整數值。
比奈公式的這種實現在計算上是高效的，因為它只需要幾個簡單的算術運算就可以計算斐波那契數列的任何一項，而不需要計算前面的所有項。
這由比奈公式的時間複雜度證明是O(1)，它是常數。這是因為該公式只需要一些算術運算即可計算出第 n 個斐波那契數。空間複雜度為 O(1)，它是常數，因為程序只使用了幾個變量來計算第 n 個斐波那契數。
貪心算法
貪心算法是一種技術用於解決優化問題。它的工作原理是在每一步都做出最佳決策，並希望做出的決策能夠帶來最佳解決方案。該算法遵循“貪心”策略，即在每一步始終選擇最大可能的數字。
可以使用這種方法生成斐波那契數列，方法是從兩個基本情況開始，然後遍歷系列以找到下一個號碼。
首先，將前兩個數保存在兩個變量中，然後將它們相加得到下一個斐波那契數。這個過程一直持續到生成序列中的第 n 個數字。
我們可以使用貪心算法簡單地實現一個斐波那契數列程序，如下所示:
def fibonacci(n):
如果 n=1:
返回 n
prev, curr=0, 1
for i in range(2, n+1):
prev, curr=curr, prev + curr
return curr
我們首先檢查 n 是否滿足基本情況，在這種情況下，我們返回了適當的值。否則，我們創建一個列表來存儲前兩個斐波那契數（0 和 1），然後使用循環通過添加列表中的最後兩個數字來生成序列中的下一個數字。循環一直持續到生成序列中的第n個數，此時我們返回它。
貪心算法的時間複雜度是O(n)，是線性的，因為我們需要迭代 n 次以生成序列中的第 n 個數字。空間複雜度也是 O(n)，因為我們需要在循環的每次迭代中將前兩個數字存儲在序列中。
但是，我們可以通過只存儲前兩個數字而不是目前生成的所有數字來優化空間複雜度。
四捨五入
斐波那契數列是一個重要且永恆的數學概念，在計算機科學和編程中有大量應用。使用正確的算法，您可以快速輕鬆地生成任何斐波那契數列。
一般而言，迭代和動態規劃在時間和空間複雜度方面是最有效的算法，而矩陣求冪在時間複雜度方面對於較大的n值是最有效的。就時間複雜度和空間複雜度而言，遞歸是最直觀但效率最低的。
最後，要使用的最佳算法取決於手頭的問題。因此，了解它們以了解何時使用每種方法來優化斐波那契程序的性能非常重要。
斐波那契數列程序示例常見問題解答（常見問題）
阿基米德螺線、黃金比例、斐波那契數列:有什麼聯繫?
阿基米德螺線和斐波那契數列可以通過黃金比例聯繫起來。
黃金比例是一個數學常數，等於斐波那契數列中兩個數字的比率。這個比率也可以在阿基米德螺線的形狀中找到。
因此，這三個概念是相互關聯的，在數學、科學和藝術中都有重要的應用。
生成斐波那契數時遞歸和迭代有什麼區別?
遞歸是一種函數調用自身來解決問題的技術，而迭代是一種循環結構，重複一組
遞歸是生成斐波那契數列最直接的方法，但由於其指數時間複雜度，它效率低下。迭代效率更高，可以在線性時間內計算出第 n 個數。
斐波那契數列如何應用於計算機科學和編程?
斐波那契數列有很多應用，例如在生成隨機數、圖形、樹、排序算法和數據壓縮的算法中。此外，斐波那契數列還用於密碼學和算法性能分析。
斐波那契數列的意義是什麼?
它經常被使用用於模擬自然界的生長模式，例如樹木的分枝、葉子在莖上的排列以及貝殼或鬆果中的螺旋狀。它還在技術分析中用於預測市場趨勢，在密碼學中用於生成隨機數。
斐波那契數列在自然界和藝術中有哪些例子?
黃金比例存在於許多自然現像中，例如某些植物和動物（例如菠蘿、向日葵、貝殼等）的螺旋。
它也存在於某些結構中，例如希臘雅典的帕台農神廟、貝多芬的第五交響曲等音樂、達芬奇的蒙娜麗莎等藝術，以及行星圍繞恆星運行的軌道等天文學。