【简单数学小问题7】楼梯走法问题（编辑ing）

无理想的闲鱼

题目1：有一段楼梯，一共12级台阶，规定每一步只能跨一级或者两级台阶，要登上12级台阶有多少种不同的走法？

【答案】233
答案仅供判断代码最后运行结果是否正确，代码块中不允许出现

                               
登录/注册后可看大图

                               
登录/注册后可看大图

如果你完成了第一道题，可以尝试做做下面的变式
拓展题目2：一共有n级台阶，要登上n级台阶有多少种不同的走法？
【输入示例1】有多少级台阶：12
【输出示例1】233或者233.0

【输入示例2】
【输出示例2】

如果你有更优的解法或者建议，欢迎评论！我会看实际情况给你评分

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

[/hide]

人造人

1. #include <stdio.h>
   
2. 
   
3. size_t stair(size_t s, size_t n, size_t init) {
   
4.     if(s > n) return init;
   
5.     if(s == n) return init + 1;
   
6.     return stair(s + 1, n, init) + stair(s + 2, n, init);
   
7. }
   
8. 
   
9. int main(void) {
   
10.     printf("%zu\n", stair(0, 12, 0));
    
11.     return 0;
    
12. }
    

复制代码

tommyyu

1. 递归（有递归次数限制）

1. nums = {1:1, 2:2}
   
2. 
   
3. import functools
   
4. @functools.cache
   
5. def dp(n):
   
6.     try:
   
7.         return nums[n]
   
8.     except:
   
9.         return dp(n-1) + dp(n-2)
   
10. 
    
11. print(dp(int(input())))
    

复制代码

2.递归（无递归次数限制）

1. nums = {1:1, 2:2}
   
2. 
   
3. import functools
   
4. @functools.cache
   
5. def dp(n):
   
6.     try:
   
7.         return nums[n]
   
8.     except:
   
9.         return dp(n-1) + dp(n-2)
   
10. 
    
11. count = 500
    
12. n = int(input())
    
13. while True:
    
14.     if n < count:
    
15.         print(dp(n))
    
16.         break
    
17.     nums_ = dict()
    
18.     nums_[count], nums_[count-1] = dp(count), dp(count-1)
    
19.     nums = nums_
    
20.     count += 500
    

复制代码

3.循环

1. n = int(input())
   
2. if n == 1:
   
3.     print(1)
   
4. elif n == 2:
   
5.     print(2)
   
6. else:
   
7.     nums = [1, 2]
   
8.     i = 2
   
9.     while i < n:
   
10.         nums.append(nums[i-2] + nums[i-1])
    
11.         i += 1
    
12.     print(nums[-1])
    

复制代码

人造人

1. >>> def stair(s, n, init):
   
2. ...     if s > n: return init
   
3. ...     if s == n: return init + 1
   
4. ...     return stair(s + 1, n, init) + stair(s + 2, n, init)
   
5. ...
   
6. >>> stair(0, 12, 0)
   
7. 233
   
8. >>>
   

复制代码

嘉岳呀

感觉有点类似斐波那契

C++递推：

1. #include <iostream>
   
2. using namespace std;
   
3. int a[10001];
   
4. int main()
   
5. {
   
6.     a[1]=1;
   
7.     a[2]=2;
   
8. 
   
9.     for(int i=3;i<=12;i++)
   
10.     {
    
11.         a[i]=a[i-1]+a[i-2];
    
12.     }
    
13. 
    
14.     cout<<a[12];
    
15. 
    
16.     return 0;
    
17. }

复制代码

嘉岳呀

递归：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int a[1001];
   
4. int fib(int n)
   
5. {
   
6.     if(a[n])
   
7.     {
   
8.         return a[n];
   
9.     }
   
10.     else
    
11.     {
    
12.         a[n]=fib(n-1)+fib(n-2);
    
13.         return a[n];
    
14.     }
    
15. }
    
16. int main()
    
17. {
    
18.     a[1]=1;
    
19.     a[2]=1;
    
20. 
    
21.     cout<<fib(13);
    
22. 
    
23.     return 0;
    
24. }

复制代码

fib(12)的时候是144，可能是有个bug

嘉岳呀

题目 2：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int a[1001];
   
4. int fib(int n)
   
5. {
   
6.     if(a[n]){
   
7.         return a[n];
   
8.     }
   
9.     else{
   
10.         a[n]=fib(n-1)+fib(n-2);
    
11.         return a[n];
    
12.     }
    
13. }
    
14. int main()
    
15. {
    
16.     int n;
    
17.     cout<<"有多少级台阶："
    
18.     cin>>n;
    
19.     a[1]=1;
    
20.     a[2]=1;
    
21. 
    
22.     cout<<fib(n+1);
    
23. 
    
24.     return 0;
    
25. }

复制代码

无理想的闲鱼

嘉岳呀 发表于 2022-11-11 13:25
感觉有点类似斐波那契

C++递推：

是的，类似 斐波那契数列

zhangjinxuan

你似乎没有给数据范围
C++

1. #include <cstdio>
   
2. using namespace std;
   
3. 
   
4. long long res[100001] = {0, 1, 2}, n;
   
5. long long solve(int num) {
   
6.         if (res[num]) return res[num];
   
7.         res[num - 1] = solve(num - 1);
   
8.         res[num - 2] = solve(num - 2);
   
9.         return res[num - 1] + res[num - 2];
   
10. }
    
11. 
    
12. int main() {
    
13.         scanf("%d", &n);
    
14.         printf("%lld", solve(n));
    
15.         return 0;
    
16. }

复制代码

Python:

1. res = {}
   
2. res[1] = 1
   
3. res[2] = 2
   
4. def solve(num):
   
5.     if res.get(num): return res[num];
   
6.     res[num - 1] = solve(num - 1)
   
7.     res[num - 2] = solve(num - 2)
   
8.     return res[num - 1] + res[num - 2]
   
9. n = int(input())
   
10. print(solve(n))

复制代码

lxping

1. def findMethod(tj):
   
2.     basic_num = {1:1,2:2}
   
3.     if tj in basic_num.keys():
   
4.         return basic_num[tj]
   
5.     else:
   
6.         return findMethod(tj-1) + findMethod(tj-2)
   
7. 
   
8. findMethod(12)
   
9. 233

复制代码

hellometa

打卡学习，顺便领个币