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

zhangjinxuan

上一关：双层汉诺塔

梦想护卫舰 第11期 数楼梯

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

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

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

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

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

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

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

输入样例

5

输出样例

8

                               
登录/注册后可看大图

答案与解析

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

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

                               
登录/注册后可看大图

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

To be continue……

下一关：破译密码

最佳答案

月排行榜 / 总排行榜

tommyyu

2023-1-23 10:59:30

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

跳转到最佳答案楼层

tommyyu

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

元豪

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

代码

n = int(input())
a = 0
b = 1
o = []
for i in range(n):
    a, b = b, a + b
    o.append(b)
print(o[-1])

ba21

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

zhangjinxuan

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

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

ba21

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

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

zhangjinxuan

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

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

ExiaGN001

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

zhangjinxuan

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

对也，正确也