CHJH明亦

用户名：2247

访问量：4940

签　名：

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

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

　　自我简介：

2019级大一新生

TA的其他文章

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

你可能喜欢

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

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

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

　　作者: CHJH明亦　　　　发表时间：2019-10-12 16:03:46 浏览：4532　|　评论：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 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

CHJH明亦

TA的其他文章

你可能喜欢

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

C语言训练-自由落体问题（C语言代码）

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

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

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

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

评论区

精彩推荐

输出九九乘法表（C语言代码）

买不到的数目（C++代码）

【偶数求和】（C语言代码）

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

C语言训练-尼科彻斯定理（C语言代码）

WU-复数求和（C++代码）

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

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

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

有关字符，字符串的输入输出函数说明

CHJH明亦

TA的其他文章

你可能喜欢

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

C语言训练-自由落体问题 （C语言代码）

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

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

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

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

评论区

精彩推荐

输出九九乘法表 （C语言代码）

买不到的数目 （C++代码）

【偶数求和】 （C语言代码）

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

C语言训练-尼科彻斯定理 （C语言代码）

WU-复数求和 （C++代码）

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

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

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

有关字符，字符串的输入输出函数说明

C语言训练-自由落体问题（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

输出九九乘法表（C语言代码）

买不到的数目（C++代码）

【偶数求和】（C语言代码）

C语言训练-尼科彻斯定理（C语言代码）

WU-复数求和（C++代码）