App下載

使用Python實現(xiàn)求解斐波那契數(shù)列第n項的多種求法

猿友 2021-07-23 11:52:15 瀏覽數(shù) (14649)
反饋

斐波那契數(shù)列作為一個非常經(jīng)典的數(shù)學問題,在我們學習編程語言遞歸思想的時候,這個問題經(jīng)常被拿來應用。下面我將為大家介紹使用Python求解斐波那契數(shù)列第n項的多種算法。

斐波那契數(shù)列

首先我們來定義一下斐波那契數(shù)列:

這里寫圖片描述

即數(shù)列的第0項:

這里寫圖片描述

算法一:遞歸

遞歸計算的節(jié)點個數(shù)是O(2?)的級別的,效率很低,存在大量的重復計算。

比如:

f(10) = f(9) + f(8)

f(9) = f(8) + f(7) 重復 8

f(8) = f(7) + f(6) 重復 7

時間復雜度是O(2?),極慢

def F1(n):
    if n <= 1: return max(n, 0)  # 前兩項
    return F1(n-1)+F1(n-2)  # 遞歸

算法二:記憶化搜索

開一個大數(shù)組記錄中間結(jié)果,如果一個狀態(tài)被計算過,則直接查表,否則再遞歸計算。

總共有 n 個狀態(tài),計算每個狀態(tài)的復雜度是 O(1),所以時間復雜度是 O(n)。但由于是遞歸計算,遞歸層數(shù)太多會爆棧。

res = [None]*100000
def F2(n):
    if n <= 1: return max(n, 0)
    if res[n]: return res[n]  # 如果已存在則直接查找返回結(jié)果
    res[n] = F2(n-1)+F2(n-2)  # 不存在則計算
    return res[n]

算法三:遞推

開一個大數(shù)組,記錄每個數(shù)的值。用循環(huán)遞推計算。

總共計算 n 個狀態(tài),所以時間復雜度是 O(n)。但需要開一個長度是 n 的數(shù)組,內(nèi)存將成為瓶頸。

def F3(n):
    if n <= 1: return max(n, 0)
    res = [0, 1]
    for i in range(2,n+1):
        res.append(res[i-1]+res[i-2])
    return res[n]

算法四:遞歸+滾動變量

比較優(yōu)秀的一種解法。仔細觀察我們會發(fā)現(xiàn),遞推時我們只需要記錄前兩項的值即可,沒有必要記錄所有值,所以我們可以用滾動變量遞推。

時間復雜度還是 O(n),但空間復雜度變成了O(1)。

def F4(n):
    if n <= 1: return max(n, 0)
    fn, f0, f1 = 0, 1, 0  # fn為最終結(jié)果,f0為第0項,f1為第一項,
    for i in range(2, n+1):
        fn = f0 + f1  # 前兩項和
        f0, f1 = f1, fn  # 遞推變量
    return fn

算法五:矩陣乘法+快速冪

利用矩陣運算的性質(zhì)將通項公式變成冪次形式,然后用平方倍增(快速冪)的方法求解第 n 項。

先說通式:

這里寫圖片描述

利用數(shù)學歸納法證明:

這里的a0,a1,a2是對應斐波那契的第幾項

這里寫圖片描述

證畢。

所以我們想要的得到An,只需要求得A?,然后取第一行第二個元素即可。

如果只是簡單的從0開始循環(huán)求n次方,時間復雜度仍然是O(n),并不比前面的快。我們可以考慮乘方的如下性質(zhì),即快速冪:

這里寫圖片描述

這樣只需要 logn 次運算即可得到結(jié)果,時間復雜度為 O(logn)

def mul(a, b):  # 首先定義二階矩陣乘法運算
    c = [[0, 0], [0, 0]]  # 定義一個空的二階矩陣,存儲結(jié)果
    for i in range(2):  # row
        for j in range(2):  # col
            for k in range(2):  # 新二階矩陣的值計算
                c[i][j] += a[i][k] * b[k][j]
    return c
def F5(n):
    if n <= 1: return max(n, 0)
    res = [[1, 0], [0, 1]]  # 單位矩陣,等價于1
    A = [[1, 1], [1, 0]]  # A矩陣
    while n:
        if n & 1: res = mul(res, A)  # 如果n是奇數(shù),或者直到n=1停止條件
        A = mul(A, A)  # 快速冪
        n >>= 1  # 整除2,向下取整
    return res[0][1]

總的來說,按照文章看下來操作一遍會發(fā)現(xiàn)解斐波那契數(shù)列問題其實也不是很難,難得是自己獨立寫的時候是否有那種編程思維。本篇文章供大家學習參考,想要了解更多關(guān)于 Python 其他資料請關(guān)注W3Cschool其它相關(guān)文章!希望大家以后多多支持我們!

0 人點贊