CHJH明亦

用户名：2247

访问量：5114

签　名：

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

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

　　自我简介：

2019级大一新生

TA的其他文章

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

你可能喜欢

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

优质题解

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

　　作者: CHJH明亦　　　　发表时间：2019-10-12 16:03:46 浏览：4681　|　评论：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编程助手吧

　　评论区

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的其他文章

你可能喜欢

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

C二级辅导-分段函数（C语言代码）

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

简单的a+b （C语言代码）

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

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

评论区

精彩推荐

简单的a+b （C语言代码）

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

C语言训练-排序问题<1> （C语言代码）

printf基础练习2 （C语言代码）

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

WU-图形输出（C++代码）

完数（C语言代码）

1124题解

简单的a+b （C语言代码）

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

CHJH明亦

TA的其他文章

你可能喜欢

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

C二级辅导-分段函数 （C语言代码）

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

简单的a+b （C语言代码）

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

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

评论区

精彩推荐

简单的a+b （C语言代码）

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

C语言训练-排序问题<1> （C语言代码）

printf基础练习2 （C语言代码）

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

WU-图形输出 （C++代码）

完数 （C语言代码）

1124题解

简单的a+b （C语言代码）

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

C二级辅导-分段函数（C语言代码）

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

　　评论区

WU-图形输出（C++代码）

完数（C语言代码）