sekko

用户名：sekko

访问量：5112

签　名：

等　　级
排　　名	4662
经　　验	1657
参赛次数	0
文章发表	8
年　　龄	0
在职情况	学生
学　　校	江西农业大学
专　　业

　　自我简介：

TA的其他文章

[编程入门]自定义函数之数字后移-题解(C语言代码)
浏览：124

[编程入门]电报加密-题解(C语言代码)
浏览：157

[编程入门]结构体之时间设计-题解(C语言代码)
浏览：596

你可能喜欢

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

[递归]母牛的故事-三种题解（C语言代码）

　　作者: sekko　　　　发表时间：2020-08-24 17:25:25 浏览：667　|　评论：2　

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

###### **分析问题**
看到这道题,如果没有明显的思路
可以试着列出一些简单的数据

| 年份  |1   |  2 | 3  | 4  |  5 | 6  |  7 |  8 |
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |
| 总数  | 1  |  2 |  3 |  4 |  6 | 9  |  13 |  19 |
|  成牛 |  1 |  1 | 1  |1   |  2 |  3 |  4  | 6  |

`成牛就是可以生育的牛`

那么我们就能发现显然的规律了.
假设第N年的牛的总数为F(n)
那么前四年中 **F(n) = n**
后面的年份里 **F(n) = F(n-1) + F(n-3)**

也很好理解,某年的牛的总数量＝去年的总数+成牛所生的数量
而成牛的数量会正好与前面第三年牛总数相等,这是小牛长大的时间

那么知道了边界和递推关系,我们就可以用递归解决问题.

###### 第一种解法-递归

```c
#include<stdio.h>

//递归函数 
int dfs(int year){
	if(year<5)	//边界 
		return year;
				//递推式 
	return dfs(year-1)+dfs(year-3);
	
}

int main()
{	
	int input[20]={0};//存储输入的数 
	int i=0,j=0; 
	int n;
	//输入部分 
	//输入部分本来应该动态分配内存,但我懒
	//而且这个也确实占不到多少内存
	while(1){
		scanf("%d",&n);
		if(n == 0) break;
		input[i]=n;
		i++;
	}
	//输出部分 
	while(i--){
		printf("%d\n",dfs( input[j++] )); 
	}
	
	
	return 0;
}
```
递归虽然简单,但是,时间复杂度极高
我试了一下 第55年 在我的电脑上算了大概有1s
这样的答案可能会超时,所以要改进.
###### 第二种解法-带有记忆化搜索的递归

#include<stdio.h>
    
    //记忆化搜索 
    int answer[56]={0};   //存储每年的答案
    					  //因为不可能某一年为0,所以以0判断空 
    
    int dfs(int year){
    	
    	if(year<5)
    		return year;
    	//后面的年份返回的都将是数组中的年份 
    	if( answer[year]==0 ) 
    		answer[year]=dfs(year-1)+dfs(year-3);
    	return answer[year];
    	
    	
    }
    
    int main()
    {	
    	int input[20]={0};
    	int i=0,j=0;
    	int n;
    	//输入部分 
    	while(1){
    		scanf("%d",&n);
    		if(n == 0) break;
    		input[i]=n;
    		i++;
    	}
    	//输出部分	
    	while(i--){
    		printf("%d\n",dfs( input[j++] )); 
    	}
    	
    	return 0;
    }

###### 第三种解法-动态规划

/*动态规划就是在现有答案可以利用 
    之前的结果推断的情况下,利用数组
    来存取答案,将所有答案动态解出 */ 
    #include<stdio.h>
    int main()
    {	
    	int input[20]={0};
    	int answer[56]={0}; 
    	int i=0,j=0;
    	int n;
    	//输入数据 
    	while(1){
    		scanf("%d",&n);
    		if(n == 0) break;
    		input[i]=n;
    		i++;
    	}
    	//计算答案
    	//动态规划代码: 
    	for(int i=1;i<5;i++)
    		answer[i]=i;
    	for(int i=5;i<56;i++)
    		answer[i]=answer[i-1]+answer[i-3];
    		//与递归的代码相似,但利用循环来解决 
    	//answer[year]=dfs(year-1)+dfs(year-3);
    	
    	//输出数据 
    	while(i--){
    		printf("%d\n",answer[input[j++]]); 
    	}
    	
    	return 0;
    }

都看到这里了,不点个赞
刷个666码?

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

慢点ei等等我

写的很好的

2020-11-10 16:05:20

sekko

动态规划是个好东西

2020-08-24 22:44:48

sekko

TA的其他文章

你可能喜欢

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

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

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

【作业调度方案】（C语言代码）

钟神赛车（C++代码）

[递归]母牛的故事-三种题解（C语言代码）

评论区

精彩推荐

C语言训练-计算一个整数N的阶乘（C语言代码）

回文串（C语言代码）

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

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

wu-理财计划（C++代码）

Minesweeper （C语言描述，蓝桥杯）

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

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

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

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

sekko

TA的其他文章

你可能喜欢

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

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

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

【作业调度方案】 （C语言代码）

钟神赛车 （C++代码）

[递归]母牛的故事-三种题解（C语言代码）

评论区

精彩推荐

C语言训练-计算一个整数N的阶乘 （C语言代码）

回文串 （C语言代码）

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

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

wu-理财计划 （C++代码）

Minesweeper （C语言描述，蓝桥杯）

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

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

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

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

【作业调度方案】（C语言代码）

钟神赛车（C++代码）

　　评论区

C语言训练-计算一个整数N的阶乘（C语言代码）

回文串（C语言代码）

wu-理财计划（C++代码）