原题链接：[递归]母牛的故事
解题思路:
第n年的母牛的来源分别来自于前一年剩下的和往前推3年的母牛（能生的母牛，最早的也算在里面）
| 第一年 | 第二年 | 第三年 | 第四年 | 第五年 | 第六年 |
| 1 | 2 | 3 | 4 | 4(第四年)+2(第二年)=6 f(5-1) + f(5-3) = 6 f(4) + f(2) = 6 | 6(第五年)+3(第三年)=9 f(6-1) + f(6-3) = 9 f(5) + f(3) = 9 |
6 = 前一年剩下的4头牛+（第2年新产的母牛刚具有生育能力生下的1头+最早的母牛1头）
解题公式：f(n) = f(n-1) + f(n-3)
注意事项:
解法1 递归
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n==0)break;
System.out.println(f(n));
}
}
public static int f(int n){
//前四天没有母牛出生
if(n<=4){
return n;
}
//上一天出生数加前三天的出生数
return f(n-1)+f(n-3);
}
}解法2 记忆型递归+剪枝 避免计算重复子问题
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n==0)break;
System.out.println(f(n));
}
}
public static Integer[] arr = new Integer[999];
public static int f(int n){
//前四天没有母牛出生
if(n<=4){
arr[n]=n;
return n;
}
//剪枝避免计算重复子问题
if(arr[n]!=null){
return arr[n];
}
//记住存储结果 以便复用
arr[n]=f(n-1)+f(n-3);
return arr[n];
}
}解法3 动态规划
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int [] arr = new int[999];
while(true){
int n = sc.nextInt();
if(n==0)break;
for(int i = 1;i <= n;i++ ){
//前四天没有母牛出生
if(i<=4){
arr[i]=i;
}else{
arr[i]=arr[i-1]+arr[i-3];
}
}
System.out.println(arr[n]);
}
}
}0.0分
91 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
int f[55]={1,2,3,4,6}; for(int i=5;i<55;i++) { f[i]=f[i-1]+f[i-3]; } int a[55]; for (int i=0;i<55;i++) { scanf("%d",&a[i]); if(a[i]==0)break; printf("%d\n",f[a[i]-1]); } return 0;int main() { while(1){ int n,c; n = c = 0; scanf("%d", &n); for (int a = 0; a <= n; a++) { if (a > 4) { c += a - 4; } } n += c; if (n == 0) break; printf("%d\n", n); } return 0; } 为啥我这只对了一半，有没有大佬帮忙解决~~#include<stdio.h> int main(){ int a; int b; while(1){ scanf("%d",&a); if(a<=3){ b=a; } else{ b=3+((1+a-3)*(a-3))/2; } printf("%d\n",b); } return 0; } 直接等差数列求和不是更简单@hyf #include <stdio.h> #include <stdlib.h> #define MAX_N 1000 // 假设输入的最大值不会超过这个数 int memo[MAX_N + 1]; // 用于存储已计算结果的数组 int fun(int n) { if (memo[n] != -1) { // 如果结果已经被计算过，则直接返回 return memo[n]; } if (n < 4) { memo[n] = n; // 存储结果 return n; } else { memo[n] = fun(n - 1) + fun(n - 3); // 递归计算并存储结果 return memo[n]; } } int main() { int n; // 初始化记忆化数组为-1，表示结果尚未计算 for (int i = 0; i <= MAX_N; ++i) { memo[i] = -1; } while (scanf("%d", &n) && n) { printf("%d\n", fun(n)); } return 0; }