当前位置：首页 > article >正文

递推进阶与入门递归

article 2024/11/26 11:41:17

一、递推进阶，勇攀高峰

昆虫繁殖

题目描述

科学家在热带森林中发现了一种特殊的昆虫，这种昆虫的繁殖能力很强。每对成虫过X个月产Y对卵，每对卵要过两个月长成成虫。假设每个成虫不死，第一个月只有一对成虫，且卵长成成虫后的第一个月不产卵(过X个月产卵)，问过Z个月以后，共有成虫多少对？

输入格式

一行，三个空格隔开的整数X Y Z。1≤X≤20,1≤Y≤20,X≤Z≤50。

输出格式

一行，一个整数，过Z个月以后，共有成虫对数。

输入输出样例

输入样例1：
1 2 8
输出样例1：
37
【耗时限制】1000ms 【内存限制】64MB

思路：

① a[i]表示第i个月成虫的对数b[i]表示第i个月新增卵的对数
②前x个月成虫数量始终为1，新增卵对数为0，a[1]…a[x]=1,b[1]…b[x]=0
③从此以后的第i个月每对成虫x个月会产生y对卵：b[i]=a[i-x]*y，
即x个月前成虫的对数乘以y新增卵每两个月成长为成虫：a[i]=a[i-1]+b[i-2],
即上个月的成虫对数+前两个月的新增卵的对数
④过了z个月后，成虫的数量，就是a[z+1]的数量

代码：

#include<bits/stdc++.h>
using namespace std;
long long a[55],b[55]; 
int main(){
	int x,y,z;
	cin>>x>>y>>z;
	for(int i=1;i<=x;i++){
		a[i]=1;
		b[i]=0;
	}
	for(int i=x+1;i<=z+1;i++){
		a[i]=a[i-1]+b[i-2];
		b[i]=a[i-x]*y;
	}
	cout<<a[z+1];
	return 0;
}

放置核物质

题目描述

欢迎大家来到智慧之门最后一关，在智慧之门最后一关有着我国最先进的科技展览，同学们想进去吗？大家异口同声说想。这个时候智慧之门门主给大家普及了一些我国核武器技术，核武器可以保家卫国，可以发电，可以说是世界上每一个国家都相当重视的课题研究，可是在核武器生产线上，要注意一定的安全。智慧之门门主说我把安全生产这个课题请同学帮我解决，门主说如果一个核电站有N个放核物质的坑，坑排列在一条直线上。如果连续M个坑中放入核物质，则会发生爆炸，于是，在某些坑中可能不放核物质。小明和同学在思考如何解决，大家把目光都投入到小明那里，因为小明是信息学社团成员。

任务：对于给定的N和M，求不发生爆炸的放置核物质的方案总数

输入格式

输入文件只一行，两个正整数N，M( 1<N<50，2≤M≤10)

输出格式

输出文件只有一个正整数S，表示方案总数。

输入输出样例

输入样例1：

4 3

输出样例1：

13

图解，思路在代码块

#include<bits/stdc++.h>
using namespace std;
long long a[55];
int main(){
	int n,m;
	cin>>n>>m;
	a[0]=1;
	a[1]=2;
	for(int i=2;i<=n;i++){
		if(i<m) a[i]=a[i-1]*2;
		else if(i==m) a[i]=a[i-1]*2-1;
		else a[i]=a[i-1]*2-a[i-m-1];
	}
	cout<<a[n];
	return 0;
}
/*主要思路

定义DP数组用来计算在每一个位置上放置核物质的方法数
枚举计算每一个坑的方案数时，共有三种情况需要考虑：
当i<=m时，每一个坑都可以放或者不放，所以方案数为：dp[i]=dp[i-1]*2
当i==m时，每一个坑也都可以放或者不放，但是要考虑一种前m个坑都被放置了的情况，即方案数为：dp[i]=dp[i-1]*2-1
当i>m时，每一个坑也都可以放或者不放，但是要考虑一种往前从第i-m个坑开始都。被放置了的情况，即方案数为： dp[i]=dp[i-1]*2-dp[i-m-1]
*/