求助大佬递归和递推（python）

pallas

问题：假设一段楼梯共 15 个台阶，小明一步最多能上 3 个台阶。编写程序计算小明上这段楼梯一共有多少种方法。

劳烦大佬们写个注释，万分感谢！！

qq1151985918

1. def res(n):
   
2.     if n < 1:
   
3.         raise ValueError("ValueError")
   
4.     elif n == 1:
   
5.         return 1
   
6.     elif n == 2:
   
7.         return 2
   
8.     elif n == 3:
   
9.         return 4
   
10.     else:
    
11.         return res(n-1) + res(n-2) + res(n-3)
    
12. 
    
13. 
    
14. if __name__ == "__main__":
    
15.     print(res(15))
    

复制代码

人造人

1. #include <stdio.h>
   
2. 
   
3. void output(size_t buff[], size_t index, size_t begin, size_t step, size_t end, size_t *count) {
   
4.     if(begin > end) return;
   
5.     if(begin == end) {
   
6.         printf("%lu: ", (*count)++);
   
7.         for(size_t i = 0; i < index; ++i) {
   
8.             printf("%lu ", buff[i]);
   
9.         }
   
10.         printf("\n");
    
11.         return;
    
12.     }
    
13.     for(size_t i = 1; i <= step; ++i) {
    
14.         buff[index] = i;
    
15.         output(buff, index + 1, begin + i, step, end, count);
    
16.     }
    
17. }
    
18. 
    
19. int main(void) {
    
20.     size_t buff[1024];
    
21.     size_t count = 0;
    
22.     output(buff, 0, 0, 3, 15, &count);
    
23.     return 0;
    
24. }
    

复制代码

1. #!/usr/bin/env python
   
2. #coding=utf-8
   
3. 
   
4. def output(buff, index, begin, step, end, count):
   
5.     if begin > end: return
   
6.     if begin == end:
   
7.         print('%d: ' % count[0], end = '')
   
8.         count[0] += 1
   
9.         for i in range(index):
   
10.             print(buff[i], end = ' ')
    
11.         print('')
    
12.     for i in range(1, step + 1):
    
13.         buff[index] = i
    
14.         output(buff, index + 1, begin + i, step, end, count)
    
15. 
    
16. buff = [0] * 1024
    
17. count = [0]
    
18. output(buff, 0, 0, 3, 15, count)
    

复制代码

傻眼貓咪

C 代码：

1. #include <stdio.h>
   
2. int step(int n){ return !n ? 0 : n < 3 ? n : n == 3 ? 4 : step(n-3) + step(n-2) + step(n-1); }
   
3. int main(){
   
4.     printf("%d", step(15));
   
5.     return 0;
   
6. }

复制代码

Python 代码：

1. step = lambda n: 0 if n == 0 else n if n < 3 else 4 if n == 3 else step(n-3) + step(n-2) + step(n-1)
   
2. print(step(15))

复制代码

输出结果：

1. 5768

复制代码

kogawananari

傻眼貓咪 发表于 2021-11-7 17:17
C 代码：Python 代码：输出结果：

就当无事发生

傻眼貓咪

kogawananari 发表于 2021-11-7 18:10
结果写错了哥是189

你意思是说除了我，二楼、三楼的大佬也是错？你的189才是正确？

kogawananari

傻眼貓咪 发表于 2021-11-7 18:23
你意思是说除了我，二楼、三楼的大佬也是错？你的189才是正确？

离谱 离谱 我之前用你的和二楼的算是189 我以为你是结果写错了草

kogawananari

1. w = (3**.5)*.5j -.5
   
2. d33 = 3*(33**.5)
   
3. d19 = 19
   
4. l3 = lambda x:x**(1/3)
   
5. x = (1+l3(d19-d33)+l3(d19+d33))/3
   
6. y = (1+l3(d19-d33)*w+l3(d19+d33)*w.conjugate())/3
   
7. z = (1+l3(d19-d33)*w.conjugate()+l3(d19+d33)*w)/3
   
8. 
   
9. # xyz是方程 x**3 - x**2 - x - 1 = 0的3个解
   
10. def tori(n,a,b,c):
    
11.     return (a**n)/(a-b)/(a-c)
    
12. def T(n):
    
13.     n += 2
    
14.     return (tori(n,x,y,z)+tori(n,y,x,z)+tori(n,z,x,y)).real
    
15. 
    
16. print(T(15))
    
17. print(T(50))
    

复制代码

输出

1. 5767.999999999993
   
2. 10562230626641.951

复制代码