本篇記錄了斐波那契數(shù)列的Python實(shí)現(xiàn)：遞歸與循環(huán)兩種解法，以及一些化用的題目。

Python實(shí)現(xiàn)

遞歸

按傳統(tǒng)的遞歸方式，簡(jiǎn)潔、優(yōu)雅。寫(xiě)出來(lái)卻是的算法

def fibo(n):
    """肥波那契函數(shù)"""
    if n < 3:
        return 1
    else:
        return fibo(n-1) + fibo(n-2)

的算法

上面“簡(jiǎn)潔”的算法其實(shí)重復(fù)算了好多項(xiàng)。比如算fibo(6)，它就算了三個(gè)fibo(3)、五個(gè)fibo(2)。從理論上分析，只要不多算，那就是的算法——大約是算了n次fibo(n-1) + fibo(n-2)。

思路也很簡(jiǎn)潔：構(gòu)建一個(gè)循環(huán)，在每次循環(huán)中，都有兩個(gè)變量?jī)?chǔ)存下一次循環(huán)的fibo(n-1)與fibo(n-2)。當(dāng)然，循環(huán)開(kāi)始和終止的邊界條件是需要注意的。（拿幾個(gè)數(shù)去試一試就行了）

def fibo(n):
    if n < 3:
        return 1
    frist = 1
    second = 1
    third = 1  # 沒(méi)有這個(gè)會(huì)怎樣？
    count = 3
    while count <= n:
        third = second + frist
        frist = second
        second = third
        count += 1
    return third

if __name__ == '__main__':
    print(fibo(2))  # 1
    print(fibo(6))  # 8

還有一種簡(jiǎn)潔的寫(xiě)法：

    """假設(shè)輸入值為整數(shù)，第1項(xiàng)為零。"""
    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return a

變體

跳臺(tái)階12

一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳一級(jí)或者兩級(jí)，求總共有多少種跳法？

1. 假設(shè)存在函數(shù)，使得即為所求；
2. 當(dāng)臺(tái)階數(shù)和時(shí)，（沒(méi)有跳法是為一種跳法）；
3. 當(dāng)時(shí)，；

看得出來(lái)是斐波那契數(shù)列嗎？就用上面的算法就行了嗎？檢驗(yàn)一下，兩級(jí)臺(tái)階的時(shí)候，總共2種跳法，寫(xiě)個(gè)測(cè)試，發(fā)現(xiàn)輸出是1 ！= 2。。（好吧，肉眼可見(jiàn)）

def fibo(n):
    """假設(shè)輸入值為整數(shù)"""
    [...]

def test_two():
    assert fibo(2) == 2  # error，1 ！= 2

怎么回事？分析得不對(duì)嗎？原來(lái)，函數(shù)fibo(n)里的n=1代表第一種情況，而這里的第一種情況是臺(tái)階數(shù)n = 0。故可把輸入改成fibo(n - 1)，或者把函數(shù)里的參數(shù)改一改。

跳臺(tái)階123

一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳一級(jí)、兩級(jí)或者三級(jí)，求總共有多少種跳法？

改一下就好，理解不了就先用定義把寫(xiě)個(gè)代碼：

def result123(n):
    """假設(shè)輸入值為整數(shù)"""
    if n <= 1: return 1
    elif n == 2: return 2
    elif n == 3: return 4
    frist = 1
    second = 2
    third = 4
    for i in range(4, n + 1):
        result = frist + second + third
        frist = second
        second = third        
        third = result
    return result

if __name__ == '__main__':
    print(result123(2))  # 2
    print(result123(3))  # 4
    print(result123(4))  # 7
    print(result123(5))  # 13

跳臺(tái)階23

一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳兩級(jí)或者三級(jí)，求總共有多少種跳法？

還是差不多，只是要從頭分析?？梢詸z驗(yàn)一下：

def result23(n):
    """假設(shè)輸入值為整數(shù)"""
    if n <= 4: return 1
    elif n <= 6: return 2
    frist = 1  # n = 4
    second = 2  # n = 5
    third = 2  # n = 6
    for i in range(7, n + 1):
        result = frist + second
        frist = second
        second = third        
        third = result
    return result

if __name__ == '__main__':
    print(result23(4))  # 1
    print(result23(6))  # 2
    print(result23(7))  # 3
    print(result23(10))  # 7

跳臺(tái)階n

一次可以跳上1級(jí)臺(tái)階，也可以跳上2級(jí)……它也可以跳上n級(jí)。求總共有多少種跳法。

還是先分析：

求個(gè)指數(shù)總會(huì)吧？