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日
    浏览(33)
  • 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日
    浏览(37)
  • 由数据范围反推算法复杂度以及算法内容

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

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

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

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

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

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

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

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

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

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

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

    2024年02月07日
    浏览(33)
  • 【算法】斐波那契数列与台风的故事

    在小岛的一个海滨小镇上,住着一个名叫苏菲的女孩。苏菲一家人靠海为生,她的生活简单而朴素,与大自然和谐共生。每天,苏菲都会来到海边,欣赏那美丽的日出和日落,感受着大海的呼吸。 然而,小岛的美丽风光并非一成不变。每年夏季,热带气旋活跃,台风频繁登陆

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

    如果数列 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日
    浏览(48)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包