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

4806 阅读 8 评论 0 点赞

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

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

我们试着考虑一下从递推的方式解决本题，最重要的是什么？
对于一个动态规划问题，最重要也是最难的部分在于“状态转移方程”。为了推导出这个状态转移方程，我们不妨在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分

16 人评分

本文分类：题解列表
浏览次数：4806 次浏览
发布日期：2019-10-12 16:03:46
本文链接：https://blog.dotcpp.com/a/62064

上一篇 > 猴子吃桃的问题-题解(C++代码)【逆向思考反向求解】
下一篇 > 蓝桥杯算法提高VIP-三个整数的排序-题解(Java代码)

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 8 条评论

jhon 2年前回复TA

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

唐鑫 3年前回复TA

@旅人RZJ 是的

CHJH明亦 4年前回复TA

@吃了一大碗呢 第一点是主函数里的if似乎没什么用；第二点是对于你的fab函数，递归下去的话并没有返回什么东西回来，只是输出了一些东西，改成“return 1；return 2;return 3;”就可以了

吃了一大碗呢 4年前回复TA

#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;
}不知道哪里错了

CHJH明亦 4年前回复TA

@旅人RZJ 从题里给的样例来看，题目的意思是第一年不生小牛，或者你可以想象成，第一年刚获得了一头生过小母牛的母牛

旅人RZJ 4年前回复TA

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

皮怪 5年前回复TA

@皮怪 第8年

皮怪 5年前回复TA

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

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

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 8 条评论

发表评论 取消回复

评论列表共有 8 条评论

发表评论取消回复