[已解决][递归]母牛的故事

逃兵

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

输入
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

输出
对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

样例输入
2
4
5
0

样例输出
2
4
6


要求：当n数值较大时，程序速度尽可能快

最佳答案

月排行榜 / 总排行榜

qq1151985918

2021-2-7 11:15:54

逃兵 发表于 2021-2-7 11:10
答案是正确的，但是运行getnum(54)速度非常缓慢

1. import functools
   
2. 
   
3. @functools.lru_cache()
   
4. def getnum(year):
   
5.     if year > 1:
   
6.         num = getnum(year - 1) + getnum(year - 3)
   
7.         return num
   
8.     else:
   
9.         return 1
   
10.    
    
11. while True:
    
12.     n = input("输入n:")
    
13.     if n == "0":
    
14.         break
    
15.     print(getnum(int(n)))

复制代码

跳转到最佳答案楼层

小甲鱼的铁粉

1. #include<stdio.h>
   
2. 
   
3. 
   
4. int main()
   
5. {
   
6.     int n;
   
7.     int count[70];
   
8.     count[0] = count[1] = count[2] = 1;
   
9.     count[3] = 1;
   
10.     while(1)
    
11.     {
    
12.         scanf("%d",&n);
    
13.         if(n == 0)
    
14.             break;
    
15.         int index = 1;
    
16.         while(index <= n)
    
17.         {
    
18.             count[index+3] = count[index+2] + count[index];
    
19.             index++;
    
20.         }
    
21.         printf("%d",count[n+2]);
    
22.     }
    
23. 
    
24.     return 0;
    
25.    
    
26. }
    
27. 
    

复制代码

qq1151985918

1. import functools
   
2. 
   
3. @functools.lru_cache()
   
4. def getnum(year):
   
5.     if year > 1:
   
6.         num = getnum(year - 1) + getnum(year - 3)
   
7.         return num
   
8.     else:
   
9.         return 1
   
10.    
    
11. while True:
    
12.     n = input("输入n:")
    
13.     if n == "0":
    
14.         break
    
15.     print(getnum(int(n)))

复制代码

逃兵

小甲鱼的铁粉 发表于 2021-2-7 10:19

python

小甲鱼的铁粉

1. count = []
   
2. 
   
3. count.append(1)
   
4. count.append(1)
   
5. count.append(1)
   
6. count.append(1)
   
7. 
   
8. while True:
   
9.     n = eval(input())
   
10.     if n == 0:
    
11.         break
    
12.     index = 1
    
13.     while index <= n:
    
14.         result = count[index+2] + count[index]
    
15.         count.append(result)
    
16.         index += 1
    
17.     print(count[n+2])
    
18.         
    
19. 
    
20.         
    

复制代码

代码比较冗余，但是速度可以

逃兵

qq1151985918 发表于 2021-2-7 10:26

答案是正确的，但是运行getnum(54)速度非常缓慢

qq1151985918

逃兵 发表于 2021-2-7 11:10
答案是正确的，但是运行getnum(54)速度非常缓慢

1. import functools
   
2. 
   
3. @functools.lru_cache()
   
4. def getnum(year):
   
5.     if year > 1:
   
6.         num = getnum(year - 1) + getnum(year - 3)
   
7.         return num
   
8.     else:
   
9.         return 1
   
10.    
    
11. while True:
    
12.     n = input("输入n:")
    
13.     if n == "0":
    
14.         break
    
15.     print(getnum(int(n)))

复制代码

逃兵

小甲鱼的铁粉 发表于 2021-2-7 11:04
代码比较冗余，但是速度可以

运行速度很快，但是没有用到递归，有没有速度快的递归方法

qq1151985918

逃兵 发表于 2021-2-7 11:17
运行速度很快，但是没有用到递归，有没有速度快的递归方法

看我给你的新的  速度飞起

逃兵

qq1151985918 发表于 2021-2-7 11:18
看我给你的新的  速度飞起

这是什么神奇的方法，能给我讲解一下吗

qq1151985918

逃兵 发表于 2021-2-7 11:20
这是什么神奇的方法，能给我讲解一下吗

原理我也不懂啊，就是知道 这个修饰符 可以极大幅度加快递归运算速度

逃兵

qq1151985918 发表于 2021-2-7 11:23
原理我也不懂啊，就是知道 这个修饰符 可以极大幅度加快递归运算速度

好的谢谢，我写的代码也是因为效率问题一直显示超时。
学到了让递归运算起飞的新方法