题目描述
有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？
输入格式
输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0 < n < 55)，n的含义如题目中描述。 n=0表示输入数据的结束，不做处理。
输出格式
对于每个测试实例，输出在第n年的时候母牛的数量。 每个输出占一行。
这是我的代码
#include<stdio.h>
int muniujihua1(int x, int count1) {
if (x > 3) {
x = x - 3;
while(x>0) {
muniujihua1(x, count1);
count1++;
x--;
}
}
else {
count1++;
}return count1;
}
int main()
{
int n;
while (scanf_s("%d", &n)) {
int count = 0;
if (n == 0) {
break;
}
while(n>0) {
count=muniujihua1(n, count);
n--;
}
printf("%d\n", count);
}
return 0;
}
这是后来查了资料，用公式复刻后的代码
#include <stdio.h>
int muniujihua(int n) {
if (n <= 4) {
return n;
}
int dp[n + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
dp[4] = 4;
for (int i = 5; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
return dp[n];
}
int main() {
int n;
while (scanf("%d", &n)) {
if (n == 0) {
break;
}
printf("%d\n", muniujihua(n));
}
return 0;
}
想不超时，这么写，供参考：
#include <stdio.h>
int main()
{
int i,n;
int a[55]={0,1,2,3,4};
for (i = 5;i < 55; i++)
a[i] = a[i-1] + a[i-3];
while( scanf("%d",&n) && n!=0)
printf("%d\n",a[n]);
return 0;
}
递归费时间，供参考：
#include<stdio.h>
int muniujihua1(int x)
{
if (x > 1)
return muniujihua1(x - 3) + muniujihua1(x - 1);
return 1;
}
int main()
{
int n;
while (scanf("%d", &n) && n) {
int count = 0;
count=muniujihua1(n);
printf("%d\n", count);
}
return 0;
}
你写的代码我怎么没看懂呢，递归的话很简单啊，直接保留一个参数 ，return f(n-3)+f(n-1)就可以啊
还有，你确定第二个代码能通过？数组长度必须是常量啊！
我感觉你是语言特性没学好
【以下回答由 GPT 生成】
第一个代码运行超时的原因是因为它使用了递归的方式来计算母牛的数量，递归的过程中存在大量重复计算，导致计算量过大，耗费了较长的时间。
第一个代码和第二个代码的输出结果一样的原因是因为它们都是基于同样的原理进行计算的。第二个代码使用了动态规划的思想，通过存储中间结果，避免了重复计算，从而提高了效率。它构建了一个数组dp，其中dp[i]表示在第i年的时候母牛的数量。通过充分利用前面计算的结果，直接计算出dp[i]，从而避免重复计算。因此，第一个代码计算出的结果和第二个代码计算出的结果是一致的。
为了进一步优化第一个代码，可以使用迭代的方式来替代递归，避免重复计算，提高效率。以下是优化后的代码：
#include <stdio.h>
int muniujihua(int n) {
if (n <= 4) {
return n;
}
int dp[n + 1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
dp[4] = 4;
for (int i = 5; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 3];
}
return dp[n];
}
int main() {
int n;
while (scanf("%d", &n)) {
if (n == 0) {
break;
}
int count = muniujihua(n);
printf("%d\n", count);
}
return 0;
}
这样的代码可以更高效地计算出第n年的母牛数量，避免了重复计算，提高了运行效率。
【相关推荐】