一、斐波那契數(shù)列（Fibonacci sequence）

斐波那契數(shù)列（Fibonacci sequence）是一個(gè)非常神奇和有趣的數(shù)列，又被稱為黃金分割數(shù)列或兔子數(shù)列。

在數(shù)學(xué)上，斐波那契數(shù)列定義為：第一項(xiàng)F(1)=0，第二項(xiàng)F(2)=1，而后續(xù)每一項(xiàng)都是前兩項(xiàng)的和，即F(n)=F(n-1)+F(n-2)（n≥3），因此，斐波那契數(shù)列的前幾個(gè)數(shù)字是：0、1、1、2、3、5、8、13、21、34、……

此外，斐波那契數(shù)列也有通項(xiàng)公式，它可以使用無理數(shù)和冪次的形式表示數(shù)列中的任意一項(xiàng)。這個(gè)通項(xiàng)公式相對(duì)復(fù)雜，涉及黃金分割比（φ = (1+√5)/2）及其共軛（ψ = (1-√5)/2）。對(duì)于第n項(xiàng)，通項(xiàng)公式可以寫作：F(n) = (φ^n - ψ^n) / √5

在這里，φ和ψ分別是黃金分割比及其共軛，√5表示5的平方根。需要注意的是，雖然φ和ψ是無理數(shù)，但斐波那契數(shù)列的每一項(xiàng)都是整數(shù)。

二、用Python實(shí)現(xiàn)婓波那契函數(shù)

使用函數(shù)遞歸或非遞歸的方式都可以方便地計(jì)算斐波那契函數(shù)：F(1)=0，F(xiàn)(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3）

1、遞歸方法：

def fibonacci_recursive(n):
    if n <= 0:
        return "輸入錯(cuò)誤，請(qǐng)輸入正整數(shù)"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_recursive(n))

2、迭代方法：

def fibonacci_iterative(n):
    if n <= 0:
        return "輸入錯(cuò)誤，請(qǐng)輸入正整數(shù)"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        a, b = 0, 1
        # 這個(gè)循環(huán)的作用是從第2項(xiàng)開始，迭代計(jì)算斐波那契數(shù)列中的每一項(xiàng)，直到達(dá)到第 n 項(xiàng)為止。
        for _ in range(2, n):  # 循環(huán)變量 _ 是一個(gè)常用的占位符，表示我們?cè)谘h(huán)中不打算使用這個(gè)變量的值。
            a, b = b, a + b  # 在每次循環(huán)迭代中，a 和 b 的值會(huì)更新為下一對(duì)斐波那契數(shù)列中的兩個(gè)連續(xù)數(shù)字。具體來說，a 會(huì)更新為 b，而 b 會(huì)更新為 a + b。
        return b  # 循環(huán)結(jié)束后，變量 b 的值就是斐波那契數(shù)列中的第 n 項(xiàng)

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_iterative(n))

以上兩種方法中，遞歸方法雖然簡(jiǎn)潔，但是效率較低，因?yàn)橛泻芏嘀貜?fù)的計(jì)算。在實(shí)際應(yīng)用中，我們更傾向于使用迭代方法，因?yàn)樗苊饬酥貜?fù)計(jì)算，提高了效率。

3、公式法：

對(duì)于第n項(xiàng)的斐波那契數(shù)列，可以使用通項(xiàng)公式進(jìn)行計(jì)算。例如，對(duì)于第10項(xiàng)的斐波那契數(shù)列，可以使用以下公式進(jìn)行計(jì)算：
F(10) = (φ^10 - ψ^10) / √5
其中，φ和ψ分別是黃金分割比及其共軛，√5表示5的平方根。

def fibonacci_formula(n):
    if n <= 0:
        return "輸入錯(cuò)誤，請(qǐng)輸入正整數(shù)"
    elif n == 1:
        return 0
    elif n == 2:
        return 1
    else:
        return (pow((1+5**0.5)/2, n) - pow((1-5**0.5)/2, n)) / 5**0.5

if __name__ == '__main__':
    n = int(input())
    print(fibonacci_formula(n))

這段代碼是計(jì)算斐波那契數(shù)列的一種方法，具體來說，它是通過使用黃金分割比φ=(1+√5)/2來快速計(jì)算第n個(gè)斐波那契數(shù)。下面是對(duì)這段代碼的逐步解釋：

• 5**0.5：這是計(jì)算5的平方根。
• -(1+5**0.5)/2 和 (1-5**0.5)/2：這兩個(gè)表達(dá)式計(jì)算了黃金分割比φ和它的共軛ψ的值。黃金分割比φ是一個(gè)無理數(shù)，其近似值為1.618033988749895。
• -pow((1+5**0.5)/2, n) 和 pow((1-5**0.5)/2, n)：這兩個(gè)函數(shù)調(diào)用計(jì)算了φ和ψ的n次冪。
• -(pow((1+5**0.5)/2, n) - pow((1-5**0.5)/2, n)) / 5**0.5：這個(gè)表達(dá)式計(jì)算了第n個(gè)斐波那契數(shù)。通過利用φ和ψ的性質(zhì)，我們避免了直接計(jì)算φ和ψ的n次冪，從而提高了效率。

因此，這段代碼通過利用數(shù)學(xué)公式和技巧，有效地計(jì)算了斐波那契數(shù)列中的第n個(gè)數(shù)。

4、矩陣快速冪法：

def fibonacci_matrix(n):  
    if n <= 0:  
        return "輸入錯(cuò)誤，請(qǐng)輸入正整數(shù)"  
    elif n == 1:  
        return 0  
    elif n == 2:  
        return 1  
    else:  
        phi = (1+5**0.5)/2  
        psi = (1-5**0.5)/2  
        a = psi/phi**0.5  
        b = phi**n - a**n * psi**n / phi**n  
        return int(b * phi**0.5)
        
if __name__ == '__main__':
    n = int(input())
    print(fibonacci_matrix(n))

這個(gè)函數(shù)使用矩陣快速冪方法來高效地計(jì)算斐波那契數(shù)列中的第n項(xiàng)。這種方法利用了矩陣的冪運(yùn)算的性質(zhì)，避免了傳統(tǒng)的遞歸或迭代方法中的重復(fù)計(jì)算，從而大大提高了計(jì)算效率。

5、動(dòng)態(tài)規(guī)劃法：

動(dòng)態(tài)規(guī)劃是一種通過將問題分解為更小的子問題并存儲(chǔ)子問題的解決方案，以便在解決更大的問題時(shí)重復(fù)使用它們的方法。

def fibonacci_dynamic_programming(n):  
    if n <= 0:  
        return "輸入錯(cuò)誤，請(qǐng)輸入正整數(shù)"  
    # 如果n等于1，則返回斐波那契數(shù)列的第一項(xiàng)0。
    elif n == 1:  
        return 0  
    # 如果n等于2，則返回斐波那契數(shù)列的第二項(xiàng)1。
    elif n == 2:  
        return 1  
    else: 
    		 # 初始化一個(gè)長(zhǎng)度為n的列表dp，其中前兩項(xiàng)0和1是已知的斐波那契數(shù)列的前兩項(xiàng)，其余項(xiàng)初始化為0。
        dp = [0, 1] + [0] * (n-2)  
        for i in range(2, n):  # 從第三項(xiàng)開始循環(huán)計(jì)算斐波那契數(shù)列的每一項(xiàng)。
            dp[i] = dp[i-1] + dp[i-2]  # 根據(jù)斐波那契數(shù)列的定義，當(dāng)前項(xiàng)等于前兩項(xiàng)之和。
        return dp[n-1]  # 返回計(jì)算得到的斐波那契數(shù)列的第n項(xiàng)的值。
if __name__ == '__main__':
    n = int(input())
    print(fibonacci_dynamic_programming(n))

對(duì)于斐波那契數(shù)列，我們可以將其視為一個(gè)遞歸問題，其中每個(gè)數(shù)是前兩個(gè)數(shù)的和。
為了解決這個(gè)問題，我們可以使用動(dòng)態(tài)規(guī)劃來避免遞歸的重復(fù)計(jì)算。

• 我們將問題分解為更小的子問題：計(jì)算斐波那契數(shù)列的前兩項(xiàng)（0和1），然后創(chuàng)建一個(gè)列表dp來存儲(chǔ)子問題的解。dp列表的長(zhǎng)度為n，其中前兩項(xiàng)已經(jīng)填充為0和1，其余項(xiàng)初始化為0。
• 然后，它循環(huán)遍歷從第三項(xiàng)到第n項(xiàng)，根據(jù)斐波那契數(shù)列的定義（每個(gè)數(shù)是前兩個(gè)數(shù)的和）來填充列表。最后，它返回列表中的第n-1個(gè)元素，這是斐波那契數(shù)列的第n項(xiàng)。

6、緩存法：

緩存法，是一種使用記憶化（也稱為緩存）技術(shù)。記憶化是一種優(yōu)化技術(shù)，用于存儲(chǔ)已經(jīng)計(jì)算過的子問題的結(jié)果，以便在后續(xù)需要時(shí)重復(fù)使用，而不是重新計(jì)算。
使用記憶化技術(shù)的主要優(yōu)勢(shì)是避免了大量的重復(fù)計(jì)算。在遞歸計(jì)算斐波那契數(shù)列時(shí)，對(duì)于每個(gè)索引 n，都需要計(jì)算 fibonacci(n-1) 和 fibonacci(n-2)。如果沒有緩存，這將導(dǎo)致大量的重復(fù)計(jì)算。通過使用緩存，我們可以存儲(chǔ)已經(jīng)計(jì)算過的斐波那契數(shù)，并在需要時(shí)直接從緩存中獲取它們，從而提高計(jì)算效率。文章來源地址http://www.zghlxwxcb.cn/news/detail-847108.html

def fibonacci_cache(n):  
    # 這是一個(gè)字典，用于存儲(chǔ)已經(jīng)計(jì)算過的斐波那契數(shù)列的值。其鍵是計(jì)算斐波那契數(shù)的索引，值是對(duì)應(yīng)的斐波那契數(shù)。
    cache = {}  
    # 這個(gè)函數(shù)用于計(jì)算斐波那契數(shù)列的第 n 項(xiàng)。
    def fibonacci(n):  
        if n in cache:  
            return cache[n] 
        elif n <= 0:  # 添加此條件檢查
            raise ValueError("輸入的數(shù)字應(yīng)為正整數(shù)")  # 當(dāng)n為負(fù)數(shù)時(shí)引發(fā)異常 
        elif n == 1:  
            result = 0  
        elif n == 2:  
            result = 1  
        # 對(duì)于其他 n，使用遞歸的方式計(jì)算斐波那契數(shù)列的第 n 項(xiàng)。
        # 遞歸地調(diào)用 fibonacci(n-1) 和 fibonacci(n-2)，并將它們的和存儲(chǔ)在 result 中。
        else:  
            result = fibonacci(n-1) + fibonacci(n-2)  
        cache[n] = result  # 將計(jì)算得到的 result 作為鍵 n 的值存儲(chǔ)在 cache 中，以便下次可以直接從緩存中獲取該值。
        return result  
    return fibonacci(n)
    
if __name__ == '__main__':
    n = int(input())
    print(fibonacci_cache(n))

到了這里，關(guān)于Python婓波那契數(shù)列（Fibonacci sequence）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！