一只青蛙一次可以跳上 1 級(jí)臺(tái)階，也可以跳上2 級(jí)爆阶。求該青蛙跳上一個(gè)n 級(jí)的臺(tái)階總共有多少種跳法窍育。
輸入格式:
首先輸入數(shù)字n遂铡，代表接下來(lái)有n組輸入截亦，50>=n>=0,然后每行一個(gè)數(shù)字爬泥，代表臺(tái)階數(shù)，數(shù)字為小于60的整數(shù)
輸出格式:
對(duì)每一組輸入魁巩，輸出青蛙的跳法。
輸入樣例:
3
1
2
3
輸出樣例:
1
2
3
用斐波那契數(shù)列解決姐浮。
直接用遞歸會(huì)超時(shí)谷遂，所以用list將前面計(jì)算過(guò)的數(shù)值保存下來(lái)。這樣后面需要計(jì)算時(shí)直接取值就可以了卖鲤。
def fun(n):
if li[n] != 0:
return li[n]
else:
li[n] = fun(n-1) + fun(n-2)
return li[n]
if __name__ == "__main__":
li = [0 for n in range(10001)]
li[0] = 0
li[1] = 1
li[2] = 2
n=0
n = int(input())
for i in range(n):
num = int(input())
print(fun(num))
CDSN有一個(gè)大佬寫了斐波那契數(shù)列的算法和相應(yīng)的性能測(cè)試： Python中斐波那契數(shù)列的四種寫法
