[已解决]梦想护卫舰 第11期 数楼梯

zhangjinxuan

上一关：双层汉诺塔

梦想护卫舰 第11期 数楼梯

你们根据野人所说的来到了神庙

神庙有一个长——长——的——楼梯，都有 n 层呢

不二看见了，惊讶的说道：

天哪，这么长的楼梯，要是每次只走一步或者两步，那有多少种走法啊？

所以……到底有多少种走法呢？你解决不二的疑惑嘛？

输入格式
一个整数 n，表示楼梯数量，1 <= n <= 1000

输出格式
一个整数，表示有多少走法

输入样例

1. 5

复制代码

输出样例

1. 8

复制代码

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

最佳战士
名字：tommyyu
奖励：最佳答案+5鱼币5荣誉

                               
登录/注册后可看大图

走过了楼梯，看见神庙的门需要密码……

To be continue……

下一关：破译密码

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-23 10:59:30

1. x = {0:1, 1:1, 500:225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626, 501:365014740723634211012237077906479355996081581501455497852747829366800199361550174096573645929019489792751}
   
2. @__import__('functools').cache
   
3. def fib(n): return x[n] if n in x else fib(n-1)+fib(n-2)
   
4. print(fib(int(input())))

复制代码

跳转到最佳答案楼层

tommyyu

1. x = {0:1, 1:1, 500:225591516161936330872512695036072072046011324913758190588638866418474627738686883405015987052796968498626, 501:365014740723634211012237077906479355996081581501455497852747829366800199361550174096573645929019489792751}
   
2. @__import__('functools').cache
   
3. def fib(n): return x[n] if n in x else fib(n-1)+fib(n-2)
   
4. print(fib(int(input())))

复制代码

元豪

研究了一下，发现这不就是更改版斐波那契数列吗~

代码

1. n = int(input())
   
2. a = 0
   
3. b = 1
   
4. o = []
   
5. for i in range(n):
   
6.     a, b = b, a + b
   
7.     o.append(b)
   
8. print(o[-1])
   

复制代码

ba21

答案和楼上不一样，理解错误。

zhangjinxuan

tommyyu 发表于 2023-1-23 10:59

哈哈，简单题就喜欢玩花样对吧

ba21

效率还是个问题
优化了下代码：

1. from time import time
   
2. n=1000000
   
3. t1 =time()
   
4. f= [1, 2]
   
5. for i in range(2, n):
   
6.     f.append(f[0] + f[1])
   
7.     del f[0]
   
8. t2=time()
   
9. print(t2-t1)
   

复制代码

zhangjinxuan

ba21 发表于 2023-1-23 18:18
效率还是个问题
优化了下代码：

效率不是问题，因为楼梯最多有 n 层，所以时间复杂度就是 O n

ExiaGN001

1. ans[i]=ans[i-1]+ans[i-2]；
   
2. 特别地，
   
3. ans[0]=0,ans[1]=1;

复制代码

zhangjinxuan

ExiaGN001 发表于 2023-2-2 13:23

对也，正确也