一只青蛙一次可以跳上 1 级台阶，也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法。
输入格式:
首先输入数字n，代表接下来有n组输入，50>=n>=0,然后每行一个数字，代表台阶数，数字为小于60的整数
输出格式:
对每一组输入，输出青蛙的跳法。
输入样例:
3
1
2
3
输出样例:
1
2
3
用斐波那契数列解决。
直接用递归会超时，所以用list将前面计算过的数值保存下来。这样后面需要计算时直接取值就可以了。
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有一个大佬写了斐波那契数列的算法和相应的性能测试： Python中斐波那契数列的四种写法
网友评论