Python實作斐波那契數列與跳台階變體

本篇記錄了斐波那契數列的Python實作：遞歸與循環兩種解法，以及一些化用的題目。

Python實作

遞歸

按傳統的遞歸方式，簡潔、優雅。寫出來卻是 O ( n 2 ) O(n^2) O(n2)的算法

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

O ( n ) O(n) O(n)的算法

上面“簡潔”的算法其實重複算了好多項。比如算

fibo(6)

，它就算了三個

fibo(3)

、五個

fibo(2)

。從理論上分析，隻要不多算，那就是 O ( n ) O(n) O(n)的算法——大約是算了n次

fibo(n-1) + fibo(n-2)

。

思路也很簡潔：建構一個循環，在每次循環中，都有兩個變量儲存下一次循環的

fibo(n-1)

與

fibo(n-2)

。當然，循環開始和終止的邊界條件是需要注意的。（拿幾個數去試一試就行了）

def fibo(n):
	if n < 3:
		return 1
	frist = 1
	second = 1
	third = 1  # 沒有這個會怎樣？
	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
           

當然，這個算法也有一個簡潔的版本，隻是不便于拓展和了解：

def fibo(n):
	"""假設輸入值為整數，第1項為零。"""
	first, second = 0, 1
	for i in range(2, n + 1):
		first, second = second, first + second
	return first
           

變體

跳台階12

一個台階總共有n級，如果一次可以跳一級或者兩級，求總共有多少種跳法？

1. 假設存在函數 f f f，使得 f ( n ) f(n) f(n)即為所求；
2. 當台階數 n = 0 n=0 n=0和 n = 1 n=1 n=1時， f ( n ) = 1 f(n)=1 f(n)=1（沒有跳法是為一種跳法）；
3. 當 n > 1 n\gt 1 n>1時， f ( n ) = f ( n − 1 ) + f ( n − 2 ) f(n) = f(n-1) + f(n-2) f(n)=f(n−1)+f(n−2)；

看得出來是斐波那契數列嗎？就用上面的算法就行了嗎？檢驗一下，兩級台階的時候，總共2種跳法，寫個測試，發現輸出是1 ！= 2。。（好吧，肉眼可見）

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

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

怎麼回事？分析得不對嗎？原來，函數

fibo(n)

裡的n=1代表第一種情況，而這裡的第一種情況是台階數n = 0。故可把輸入改成

fibo(n - 1)

，或者把函數裡的參數改一改。

跳台階123

一個台階總共有n級，如果一次可以跳一級、兩級或者三級，求總共有多少種跳法？

改一下就好，了解不了就先用定義把寫個代碼：

def result123(n):
	"""假設輸入值為整數"""
    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
           

跳台階23

一個台階總共有n級，如果一次可以跳兩級或者三級，求總共有多少種跳法？

還是差不多，隻是要從頭分析。可以檢驗一下：

def result23(n):
	"""假設輸入值為整數"""
    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
           

跳台階n

一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求總共有多少種跳法。

還是先分析：

f ( n ) = f ( n − 1 ) + f ( n − 2 ) + ⋯ + f ( 1 ) f ( n − 1 ) = f ( n − 2 ) + f ( n − 3 ) + ⋯ + f ( 1 ) f ( n ) − f ( n − 1 ) = f ( n − 1 ) f ( n ) = 2 f ( n − 1 ) = 2 n − 1 f(n) = f(n-1) + f(n-2) + \dots + f(1)\\f(n-1) = f(n-2) + f(n-3) + \dots + f(1)\\f(n)-f(n-1) = f(n-1)\\ f(n) = 2f(n-1)=2^{n-1} f(n)=f(n−1)+f(n−2)+⋯+f(1)f(n−1)=f(n−2)+f(n−3)+⋯+f(1)f(n)−f(n−1)=f(n−1)f(n)=2f(n−1)=2n−1

求個指數總會吧？