| 等 级 | |
| 排 名 | 367 |
| 经 验 | 5061 |
| 参赛次数 | 0 |
| 文章发表 | 1 |
| 年 龄 | 99 |
| 在职情况 | 学生 |
| 学 校 | 望子成龙小学 |
| 专 业 |
自我简介：
TA的其他文章
| 1004: [递归]母牛的故事 浏览：17943 |
你可能喜欢
C语言程序设计教程（第三版）课后习题8.5 （C语言代码）浏览：582 |
指针做法浏览：865 |
点我有惊喜！你懂得！浏览：1219 |
printf基础练习2 （C语言代码）浏览：591 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）浏览：1277 |
原题链接：[递归]母牛的故事
解题思路:
打表理清思路先，把牛家分大牛、三岁牛宝、两岁牛宝、一岁牛宝（虚岁，出生就是一岁啦）
在第5年时，牛宝开始陆续长成大牛，三岁牛宝就变成了大牛
同理，两岁牛宝变三岁牛宝，一岁牛宝变两岁牛宝
而新的一岁牛宝则是去年的大牛跟三岁牛宝的总牛数（三岁牛宝今年长成大牛也开始生小牛宝了）
思路理清后，就要求递推公式了，把4种牛分别用字母标记：
大牛a[]、三岁牛宝b[]、两岁牛宝c[]、一岁牛宝d[]以及牛头数s[]
可以得出第n年的各个公式：
a[n] = a[n-1]+b[n-1]
b[n] = c[n-1]
c[n] = d[n-1]
d[n] = a[n-1]+b[n-1] = a[n]
则总牛数 s[n]=a[n]+b[n]+c[n]+d[n]
= a[n-1]+b[n-1]+c[n-1]+d[n-1]+a[n-1]+b[n-1]
= s[n-1]+a[n-2]+b[n-2]+c[n-2]
= s[n-1]+a[n-3]+b[n-3]+c[n-3]+d[n-3]
= s[n-1]+s[n-3]
根据递推公式可以写出基本的递归函数如下：
int fab(int month) {
if(month < 4) {
return month;
} else {
return fab(month-1)+fab(month-3);
}
}但递归在月份大的时候空间复杂度跟时间复杂度都特别高，故需再用动态规划思路，在递归的过程中不断记录计算过的月份的牛头数，需要的时候可以直接调用
参考代码:
应题目要求使用递归：
#include<iostream>
using namespace std;
long long cow[56] = {0,1,2,3,4}; // 在main函数外定义的数组会全部自动初始化为0
long long fab(int month) {
if(cow[month] == 0) { // 没有算过的月份，数组内存的是0
cow[month] = fab(month-1) + fab(month-3);
return cow[month];
} else {
return cow[month];
}
}
int main () {
int n;
while(scanf("%d", &n) && n) cout << fab(n) << endl;
return 0;
}或者直接用递推公式：
#include<iostream>
using namespace std;
int main () {
int cow[56] = {0,1,2,3,4};
for(int i = 4; i < 55; i ++) cow[i] = cow[i-1] + cow[i-3];
int n;
while(scanf("%d", &n) && n) cout << cow[n] << endl;
return 0;
}0.0分
246 人评分
评论区
#include<iostream>
#include<vector>
using namespace std;
int main()
{
while (true)
{
int n, num = 1;
cin >> n;
if (n == 0)
{
break;
}
vector<int>age;
age.push_back(0);
for (int i = 2; i <= n; i++)
{
int numplus = 0;
for (int j = 0; j < num; j++)
{
age[j] += 1;
if (age[j] >= 4)
{
numplus++;
}
}
num = num + numplus + 1;
for (int k = 0; k < (numplus + 1); k++)
{
age.push_back(0);
}
}
cout << num << endl;
}
return 0;
}为什么不可以
2024-04-07 22:20:11
#include <iostream>
#include <string>
using namespace std;
#define N 55
int cow[N];
void b(int x);
int main()
{
int n[N];
b(N);
int i=0;
do
{
cin >> n[i];
} while (n[i++] != 0);
for (int j = 0; j < i-1; j++)
{
cout << cow[n[j]] << endl;
}
return 0;
}
void b(int x)
{
for (int i = 1; i <= x; i++)
{
if (i < 4)
cow[i] = i;
else
cow[i] = cow[i - 1] + cow[i - 3];
}
}
2024-03-24 15:39:52
uu们，为啥我这个不行
#include<iostream>
using namespace std;
long scn[5]={0};
long mcnum=1;
void cowreprouce(int year)
{ if(year<=0)
return ;
scn[4]+=scn[3];
scn[3]=scn[2];
scn[2]=scn[1];
scn[1]=0;
mcnum+=scn[4];
scn[4]=0;
scn[1]+=mcnum;
if(--year>0)
cowreprouce(year);
}
int main()
{
int n;
long res;
cin>>n;
if(n==0)
return 0;
n-=1;
cowreprouce(n);
res=mcnum+scn[1]+scn[2]+scn[3]+scn[4];
cout<<res;
return 0;
}
2024-01-27 21:26:34
uq_82684157213 2024-03-05 13:36:32 |
UJH
为什么这个不行？
#include<iostream>
using namespace std;
int f(int n);
int f(int n)
{
if (n <=4)
{
return n;
}
else
{
return f(n - 1) + 1 + f(n - 4);
}
}
int main()
{
int n,num[100],i=1;
cin >> n; num[0] = n;
while (n != 0)
{
cin >> n;
num[i] = n;
i++;
}
cout << endl;
for (int j = 0; j < i+1; j++)
{
if (num[j] != 0)
{
int sum = f(num[j]);
cout << sum << endl;
}
else {
break;
}
}
system("pause");
return 0;
}
2023-11-12 09:47:11
#include<stdio.h>
int num(int n){
if(n < 5) return n;
else return num(n-1)+num(n-3);
}
int main(){
int n;
while(scanf("%d",&n) && n)
printf("%d\n",num(n));
}
returrn 0;
}
注意要从n<5开始，这样时间才不会超
2023-01-31 19:24:13
精彩推荐
C语言程序设计教程（第三版）课后习题8.2 （Java代码）浏览：2268 |
C语言训练-排序问题<1> （C++代码）浏览：589 |
C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）浏览：1027 |
【亲和数】 （C语言代码）浏览：492 |
C语言程序设计教程（第三版）课后习题1.5 （C语言代码）浏览：480 |
C语言程序设计教程（第三版）课后习题5.4 （C语言代码）浏览：505 |
简单的for循环浏览：1408 |
C语言程序设计教程（第三版）课后习题8.4 （C语言代码）浏览：619 |
C语言程序设计教程（第三版）课后习题8.9 （C语言代码）浏览：817 |
GC的苦恼 （C语言代码）浏览：618 |