引言：為什么斐波那契是編程“入門(mén)必修課”？

斐波那契數(shù)列（Fibonacci Sequence）是一個(gè)經(jīng)典的數(shù)學(xué)序列：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
定義為：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

它不僅是數(shù)學(xué)之美，更是編程思維的試金石。
掌握它的多種實(shí)現(xiàn)方式，意味著你真正理解了：

• 循環(huán)與遞歸
• 時(shí)間復(fù)雜度與空間復(fù)雜度
• 記憶化與動(dòng)態(tài)規(guī)劃
• 生成器與內(nèi)存優(yōu)化

方法一：【最優(yōu)】循環(huán)迭代法（推薦級(jí)）

這是最實(shí)用、最高效的寫(xiě)法，也是你寫(xiě)的版本！

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

優(yōu)點(diǎn)：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(1)
• 代碼簡(jiǎn)潔，邏輯清晰
• 支持大數(shù)計(jì)算（如 fib_iter(10000) 不會(huì)爆棧）

使用建議：

• 日常使用首選！
• 適用于絕大多數(shù)場(chǎng)景，尤其是 n 較大時(shí)

方法二：【不推薦】樸素遞歸法（反面教材）

def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

問(wèn)題：

• 時(shí)間復(fù)雜度：O(2^n) —— 指數(shù)級(jí)增長(zhǎng)，效率極低
• 空間復(fù)雜度：O(n) —— 遞歸深度
• 存在大量重復(fù)計(jì)算（如 fib_recursive(5) 會(huì)重復(fù)計(jì)算 fib_recursive(3) 兩次）

結(jié)果：

• n > 30 就明顯卡頓
• 僅用于理解遞歸思想，不要在生產(chǎn)環(huán)境使用

方法三：【推薦】記憶化遞歸（動(dòng)態(tài)規(guī)劃思想）

from functools import lru_cache
 
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

優(yōu)點(diǎn)：

• 時(shí)間復(fù)雜度：O(n)
• 空間復(fù)雜度：O(n)
• 利用緩存避免重復(fù)計(jì)算
• 代碼接近數(shù)學(xué)定義，可讀性強(qiáng)

適用場(chǎng)景：

• 學(xué)習(xí)“記憶化”、“動(dòng)態(tài)規(guī)劃”的絕佳案例
• 適合中等規(guī)模數(shù)據(jù)（如 n < 10?）

方法四：【推薦】生成器版本（內(nèi)存友好）

def fib_generator(n):
    a, b = 0, 1
    count = 0
    while count < n:
        yield a
        a, b = b, a + b
        count += 1
 
# 使用方式
for num in fib_generator(10):
    print(num, end=' ')
# 輸出：0 1 1 2 3 5 8 13 21 34

優(yōu)點(diǎn)：

• 不一次性生成所有數(shù)，節(jié)省內(nèi)存
• 支持 next() 逐個(gè)獲取
• 適合處理大數(shù)據(jù)或無(wú)限序列

適用場(chǎng)景：

• 處理大量數(shù)據(jù)（如前 100 萬(wàn)個(gè)斐波那契數(shù)）
• 流式處理、實(shí)時(shí)輸出

方法五：【高級(jí)】矩陣快速冪（超快！）

適用于：求第百萬(wàn)個(gè)斐波那契數(shù) 的極致性能需求。

def matrix_multiply(A, B):
    return [
        [A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
        [A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
    ]
 
def matrix_power(mat, n):
    if n == 1:
        return mat
    if n % 2 == 0:
        half = matrix_power(mat, n // 2)
        return matrix_multiply(half, half)
    else:
        return matrix_multiply(mat, matrix_power(mat, n - 1))
 
def fib_fast(n):
    if n <= 1:
        return n
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = matrix_power(base_matrix, n)
    return result_matrix[0][1]

優(yōu)點(diǎn)：

• 時(shí)間復(fù)雜度：O(log n)
• 極速計(jì)算，適合超大數(shù)

適用場(chǎng)景：

• 求第 10? 個(gè)斐波那契數(shù)
• 算法競(jìng)賽、高性能計(jì)算

性能對(duì)比總結(jié)表

最佳實(shí)踐建議

• 日常開(kāi)發(fā) → 用循環(huán)迭代法（你寫(xiě)的那個(gè)）
• 學(xué)習(xí)算法 → 用記憶化遞歸
• 處理大數(shù)據(jù) → 用生成器
• 追求極致性能 → 用矩陣快速冪

擴(kuò)展練習(xí)題（挑戰(zhàn)一下）

1. 寫(xiě)一個(gè)函數(shù)，返回前 n 個(gè)斐波那契數(shù)的列表（用生成器）
2. 寫(xiě)一個(gè)函數(shù)，判斷某個(gè)數(shù)是否為斐波那契數(shù)
3. 畫(huà)出斐波那契數(shù)列的圖形（用 matplotlib）
4. 模擬“兔子繁殖”問(wèn)題（經(jīng)典故事背景）

附錄：一鍵運(yùn)行腳本模板

"""
【推薦】斐波那契函數(shù)合集（可直接復(fù)制使用）
"""
from functools import lru_cache
 
# 1. 循環(huán)迭代（最優(yōu)）
def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a
 
# 2. 記憶化遞歸（推薦學(xué)習(xí)）
@lru_cache(maxsize=None)
def fib_memo(n):
    if n <= 1:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)
 
# 3. 生成器（內(nèi)存友好）
def fib_gen(n):
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b
 
# 測(cè)試
if __name__ == "__main__":
    print("前10個(gè)斐波那契數(shù)：")
    print(list(fib_gen(10)))

以上就是利用Python實(shí)現(xiàn)斐波那契數(shù)列的5種方法全解析的詳細(xì)內(nèi)容，更多關(guān)于Python實(shí)現(xiàn)斐波那契數(shù)列的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論