C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线)

这篇具有很好参考价值的文章主要介绍了C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
递推掌握核心:

  • 递推公式(规律)
  • 递推边界(初始化条件)
    C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
    分析题目意思:如下图
    C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
    递推式:a[n] = a[n-1]+a[n-2];
    递推边界:a[1]=1 a[2]=2

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构

#include<iostream>
using namespace std;
long long a[100],x,y,z;
int main(){ //昆虫繁衍 
	cin>>x>>y>>z;
	//x月前面 
	for(int i=1;i<=x;i++){
		a[i]=1; //一对成虫 
	} 
	//x月后面 
	for(int i=x+1;i<=z+1;i++){
		//递推公式 a[n]=a[n-1]+a[n-x-2]*y
		a[i]=a[i-1]+a[i-x-2]*y;
	} 
	cout<<a[z+1];
	return 0;
}

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
题目意思:卒从A点到B点可以走哪几条路?有前提条件:卒只能往下或往右走! 马的位置和8个控制点不能走!
C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
由于卒一直往右走,我们知道(0,3)这个P5点是被马控制的,不能走,那(0,4) 在P5的后面也走不了!

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构

  • 递推式:a[i][j]=a[i-1][j]+a[i][j-1];
#include<bits/stdc++.h>
using namespace std;
int a[30][30]; //数组存储这个坐标点的路径数 
bool flag[30][30]; //标记这个点是否能走 
int b[8][2]={{-1,-2},{1,-2},{-2,-1},{2,-1},{1,2},{-1,2},{2,1},{-2,1}};

int main(){
	int n,m,x,y;
	cin>>n>>m>>x>>y;
	flag[x][y]=true; 
	//马的坐标x,y 标记true,代表不能走 
	for(int i=0;i<8;i++){ //马的8个控制点也不能走 
		int tx = x+b[i][0]; //8个控制点的x坐标 
		int ty = y+b[i][1]; //8个控制点的y坐标 
		if(tx>=0 && tx<=n && ty>=0 && ty<=m){ //坐标满足在范围内 
			flag[tx][ty]=true; //标记true,代表不能走 
		} 
	}
	
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){ //遍历整个二维数组 
			if(flag[i][j]==true){
				a[i][j]=0; //这个点的路径为0 
			}
		    else if (i==0 && j==0){
				a[i][j]=1; //地点位置路径数为1 
			}
			else if(i==0 && j!=0){
				//单行(0,1) (0,2)的路径数由前面的位置决定!
				a[i][j] = a[i][j-1];
			}
			else if(j==0 && i!=0){
				//单列(1,0) (2,0)的路径数由前面的位置决定!
				a[i][j] = a[i-1][j];
			}
			else{ //递推规律 
				a[i][j]=a[i-1][j]+a[i][j-1];
			}
		}
	}
	cout<<a[n][m];
	return 0;
}

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
这道题比较简单,需要注意 对第a个数取模1000。 在递推式的时候就要实现,不然在输出那里因为运算的结果太大会报错!!!
递推式:f[i] = (f[i-1]+f[i-2])%1000;

#include<bits/stdc++.h>
using namespace std;
long long f[1000002]; 
int main(){
	f[1]=f[2]=1;
	int n,a;
	cin>>n;
	for(int i=3;i<=1000000;i++){ //斐波那契数列1-100000的值 
		f[i] = (f[i-1]+f[i-2])%1000; //递推式 
	}
	for(int i=1;i<=n;i++){ 
	//根据题目条件,n行,每一行有第a个数列,输出第a个斐波那契数列值 
		cin>>a;
		cout<<f[a]<<endl;
	}
	return 0;
}

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
这题也不难,只要知道递推式,递推边界即可!

很明显递推式:f[i] = (2*f[i-1]+f[i-2])%32767

#include<bits/stdc++.h>
using namespace std;
long long f[1000009]; 
int main(){
	f[1]=1;
	f[2]=2;
	int n,a;
	for(int i=3;i<=1000000;i++){
		f[i] = (2*f[i-1]+f[i-2])%32767;
	}
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a;
		cout<<f[a]<<endl;
	}
	return 0;
}

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
上台阶也是一种斐波那契数列。
递推式:a[i] = a[i-1]+a[i-2]+a[i-3];
递推边界:a[1]=1; a[2]=2; a[3]=4;

#include<iostream>
using namespace std;
long long a[100];
int main(){
	a[1]=1;
	a[2]=2;
	a[3]=4;
	int n;
	do{
		cin>>n;
		if(n==1 || n==2 || n==3){
			cout<<a[n]<<endl;
		}
		else{
			for(int i=4;i<=n;i++){
				a[i] = a[i-1]+a[i-2]+a[i-3];
			}
			if(n==0){
				return 0; 
			}
			cout<<a[n]<<endl;
		}
	}while(n!=0);
	return 0;
}

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构
1.输入二维数组 n*n 值;
2.如果某房间坐标有感染,那这个人房间位置的上下左右都要标记感染,额外判断空房间不感染;
3.遍历一遍房间如果是被标记感染的,则把房间健康的人变成感染!
4.m天次,就是重复执行 步骤2 3;
5.最后统计第m天的感染人数,并输出

//1191:流感传染
#include<bits/stdc++.h>
using namespace std;
char a[105][105];
bool flag[105][105]={0};
int main(){
	int n,m,cnt=0;
	cin>>n;
	for(int i=1;i<=n;i++){ //输入第一天值 
		for(int j=1;j<=n;j++){
			cin>>a[i][j];
		}
	}
	cin>>m;
	for(int k=2;k<=m;k++){// 第2天到第m天 
		for(int i=1;i<=n;i++){ //遍历一遍房间 
			for(int j=1;j<=n;j++){
				if(a[i][j]=='@'){ //房间的人是感染则
					//上下左右有人的房间标记感染 
					if(a[i-1][j]=='.') flag[i-1][j]=true;
					if(a[i+1][j]=='.') flag[i+1][j]=true;
					if(a[i][j-1]=='.') flag[i][j-1]=true;
					if(a[i][j+1]=='.') flag[i][j+1]=true;
				}
			}
		}
		for(int i=1;i<=n;i++){ 
		//再遍历一遍房间, 
			for(int j=1;j<=n;j++){
				if(flag[i][j]==true){ // 对感染的房间里的人改变状态,
					a[i][j]='@'; //标记生病 
				}
			}
		}
	}
	//第m天后,统计感染的的人数,并输出 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(a[i][j]=='@'){
				cnt++;
			}
		}
	}
	cout<<cnt;
	return 0;
}

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构

这道题跟“过河卒”很像,而且简单些。前提条件:只能往上或往右走! ,也就是行会变大、或列变大。 计算走的路线和。 注意单行单列只有一种走法!

  • 递推式:a[i][j]=a[i-1][j] + a[i][j-1];

C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线),算法,算法,c++,数据结构文章来源地址https://www.toymoban.com/news/detail-610690.html

#include<bits/stdc++.h>
using namespace std;
int a[21][21];
int main(){
	int m,n;
	cin>>m>>n;
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(i==1 && j!=1){ //单行(1,1) (1,2)的路径数1
				a[1][j]=1;
			}
			else if(j==1 && i!=1){ //单列(1,1) (2,1)的路径数1
				a[i][1]=1;
			}
			else{ //往上走或往右走的递推公式 
				a[i][j]=a[i-1][j] + a[i][j-1];
			}
		}
	}
	cout<<a[m][n];
	return 0;
}

到了这里,关于C++基础算法⑤——递推算法(昆虫繁殖 过河卒 Pell数列 上台阶 流感传染 移动路线)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法中的递推算法

    给定一个数的序列H0,H1,…,Hn,…若存在整数n0,使当nn0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0in)联系起来,这样的式子就叫做递推关系。 递推算法是一种简单的算法,即通过已知条件,利用特定关系得出中间推论,直至得到结果的算法。 递推算法分为顺推

    2024年02月12日
    浏览(31)
  • go语言计算推算心率算法 http服务

    为了计算心率和并且将心率计算作为http服务来运行 1 基本数据 a) hrv heart rate variability b) 呼吸 2 傅里叶变换 计算频率 高频和低频 3 隐形马尔科夫 模型 hmm 重在于推测概率 根据最近的心率计算 4 神经网络计算 hrv 5 min RR 间期 平均值标准差 sdann 24h 正常的RR间期总体标准差 s

    2024年02月16日
    浏览(35)
  • 由数据范围反推算法复杂度以及算法内容

    一般编程题目的时间限制是1秒或2秒  在这种情况下,C++代码中的操作次数控制在 为最佳。 下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择: 时间复杂度 对应的数据规模上限(1s时限) 算法 - - 高精度加减、FFT/NTT 高精度乘除 最大公约数、快速幂、数位DP 判断

    2024年03月21日
    浏览(39)
  • C/C++基础讲解(一百零一)之经典篇(打印笑脸/兔子繁殖/素数)

    很多时候,特别是刚步入大学的学子们,对于刚刚开展的计算机课程基本上是一团迷雾,想要弄明白其中的奥秘,真的要花费一些功夫,我和大家一样都是这么啃过来的,从不知到知知,懵懂到入门,每一步都走的很艰辛,课程上,大学老师基本上讲解上机实操得时间特别有

    2024年02月08日
    浏览(43)
  • 算法详解 - 神奇的兔子数列

    14天阅读挑战赛 *努力是为了不平庸~ 递归、斐波那契数列 异步社区 假设第一个月有一对初生的兔子,第2个月进入成熟期,第三个月进行生育兔子,而一对成熟的 兔子每月会生1对兔子,兔子永不死去,那么从第一对初生的兔子开始,12个月后会有多少只兔子? 不妨拿新出生

    2024年02月06日
    浏览(30)
  • 【算法Hot100系列】外观数列

    💝💝💝欢迎来到我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:kwan 的首页,持续学习,不断总结,共同进步,活到老学到老 导航 檀越剑指大厂系列:全面总

    2024年01月18日
    浏览(40)
  • 每日算法打卡:波动数列 day 16

    1214. 波动数列 题目难度:中等 题目来源:第五届蓝桥杯省赛C++ A组,第五届蓝桥杯省赛Java A组 观察这个数列: 1 3 0 2 -1 1 -2 … 这个数列中后一项总是比前一项增加2或者减少3, 且每一项都为整数 。 栋栋对这种数列很好奇,他想知道长度为 n 和为 s 而且后一项总是比前一项增

    2024年01月16日
    浏览(52)
  • C++信息学奥赛1201:菲波那契数列

    代码逻辑:首先输入一个整数n,然后输入n个整数,并将它们存入一个数组arr中。对于每个输入的整数x,通过递归调用f(x)来计算其对应的斐波那契数列值,将得到的结果存入另一个数组brr中。最后,输出数组brr的所有元素。

    2024年02月07日
    浏览(30)
  • 【算法学习】斐波那契数列模型-动态规划

            我在算法学习过程中,针对斐波那契数列模型的动态规划的例题进行了一个整理,并且根据标准且可靠一点的动态规划解题思路进行求解类似的动归问题,来达到学习和今后复习的必要。         所谓的斐波那契数列模型,即当前状态的值等于前两种状态的值之和。

    2024年02月04日
    浏览(54)
  • 【算法】斐波那契数列通项公式

    如果数列 a n a_n a n ​ 的递推公式: a n = c 1 a n − 1 + c 2 a n − 2 a_n=c_1a_{n-1}+c_2a_{n-2} a n ​ = c 1 ​ a n − 1 ​ + c 2 ​ a n − 2 ​ ------(1) 根据待定系数法,假设 a n − x a n − 1 = y ( a n − 1 − x a n − 2 ) a_n-xa_{n-1}=y(a_{n-1}-xa_{n-2}) a n ​ − x a n − 1 ​ = y ( a n − 1 ​ − x a n − 2 ​

    2023年04月24日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包