CHJH明亦

用户名：2247

访问量：4939

签　名：

明朝和醉沐春景，亦倾心盏满豪情。

等　　级
排　　名	6409
经　　验	1355
参赛次数	1
文章发表	1
年　　龄	0
在职情况	学生
学　　校	北京交通大学海滨学院
专　　业	软件工程

　　自我简介：

2019级大一新生

TA的其他文章

[递归]母牛的故事-题解(C++代码)（递推方式）
浏览：4531

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

[递归]母牛的故事-题解(C++代码)（递推方式）

　　作者: CHJH明亦　　　　发表时间：2019-10-12 16:03:46 浏览：4531　|　评论：4　

原题链接：[递归]母牛的故事

# 母牛的故事——由递归到递推
我们都知道递推（动态规划）是递归（搜索）的反向操作，本题虽然注明“【递归】”，但同样可以用递推方式解决本题。

由于本题很多题解都详细讲解了递归的方式，那么这篇题解将不再赘述递归的方式。

我们试着考虑一下从递推的方式解决本题，最重要的是什么？
对于一个动态规划问题，最重要也是最难的部分在于“状态转移方程”。为了推导出这个状态转移方程，我们不妨在Excel中制作一张表格，用于记录每年的母牛的数量，这里我们列举出前九年的母牛数量：![](/image_editor_upload/20191012031617_24550.png)

我们可以很轻易的看出从第四年开始，每年的母牛数量都等于前一年的母牛数量加上三年前的母牛数量即状态转移方程为：cows[i] = cows[i-1] + cows[i-3];

到此为止，我们已经解决了最难的部分，但是还有一些小问题，比如：我们前三年的能不能用状态转移方程表示出来。

其实我们可以直接初始化为1，2，3，但是为了整体简短些，我们换一种方式，我们可以将整个数组向后推三个位置，即前面流出三个位置用于保证cows[i-3]不越界，附初始化函数代码：
```cpp
int cows[70];
void init ()
{
	for (int i = 0;i < 70;i ++){
		cows[i] = 1;//全部赋为1，便于前三年母牛数量的增加
	}
	for (int i = 5;i < 70;i ++){
		cows[i] = cows[i-1] + cows[i-3];//状态转移方程
	}
}
```
本题对于cows开55个空间就足够~~，由于今年是建国70周年就开了70个空间~~。
由于我们将整个数据向后推移了三个空间，当我们输出答案时，也应该向后移三个空间。附AC代码：
```cpp
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
//有很多头文件其实没有用到，由于个人习惯就写上了六个，至于为什么不用<bits/stdc++.h>是因为早些版本的C++并没有整个头文件，就没有使用。
int cows[70];
void init ()
{
	for (int i = 0;i < 70;i ++){
		cows[i] = 1;
	}
	for (int i = 5;i < 70;i ++){
		cows[i] = cows[i-1] + cows[i-3];
	}
}
int main ()
{
	int n;
	init ();
	while (scanf ("%d",&n) != EOF){//使用scanf的原因是scanf较cin快一点，printf同理。
		if (n != 0){
			printf ("%d\n",cows[n+3]);//我们初始化将所有数据顺移三个单位，这里为保证结构正确也顺移三个单位。
		}
	}
	return 0;
}
```

0.0分

32 人评分

C语言网推出会员服务，提供C/C++/算法/Python等多套视频学练课程+源码资源社群答疑+私活推荐等资源，享受丰富的技术学习到变现的乐趣，以含金量和学习效果勇敢挑战同类辅导！点击了解开通

　　评论区

jhon

不应该是n+(n-4)+(n-2*4)+(n-3*4)+...吗？

2022-04-15 13:42:56

吃了一大碗呢

#include<iostream>
#include<cstdlib>
using namespace std;
int Fab(int n)
{
	if(n==1) cout<<1<<endl;
	else if(n==2) cout<<2<<endl;
	else if(n==3) cout<<3<<endl;
	else 
	{
     return Fab(n-1)+Fab(n-3);
	}
}
int main()
{
   int n;
   cin>>n;
   if(n==1)
	   return 0;
   else
    cout << Fab(n) << endl;  
      system("pause");
    return 0;
}不知道哪里错了

2020-04-12 10:26:27

旅人RZJ

为什么第一头牛第一年年初不生

2020-03-01 17:03:05

皮怪

第七年按你这个方式算，第七年不应该是19只牛吗

2019-12-11 15:28:40

CHJH明亦

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-阶乘数列（C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

（格式错误） qq290048663 碰巧告知我吧

[递归]母牛的故事-题解(C++代码)（递推方式）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

大神老白（C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

CHJH明亦

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题7.1 （C++代码）

C二级辅导-阶乘数列 （C语言代码）

A+B for Input-Output Practice (VII) （C++代码）

（格式错误） qq290048663 碰巧告知我吧

[递归]母牛的故事-题解(C++代码)（递推方式）

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C++代码）（和输入10个数排序没有区别，直接sort即可）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.3 （C语言代码）

C语言程序设计教程（第三版）课后习题3.7 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-计算：t=1-1/(2*2)-1/(3*3)-...-1/(m*m) （C语言代码）

大神老白 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

A+B for Input-Output Practice (II) （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

C二级辅导-阶乘数列（C语言代码）

　　评论区

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

C语言训练-计算：t=1-1/(22)-1/(33)-...-1/(m*m) （C语言代码）

大神老白（C语言代码）