网站开发 自学,大气企业网站欣赏,应用市场app下载安装,重庆公司免费网站建设#x1f600;前言 递推算法在计算机科学中扮演着重要的角色。通过递推#xff0c;我们可以根据已知的初始条件#xff0c;通过一定的规则推导出后续的结果#xff0c;从而解决各种实际问题。本文将介绍递推算法的基础知识#xff0c;并通过一些入门例题来帮助读者更好地理… 前言 递推算法在计算机科学中扮演着重要的角色。通过递推我们可以根据已知的初始条件通过一定的规则推导出后续的结果从而解决各种实际问题。本文将介绍递推算法的基础知识并通过一些入门例题来帮助读者更好地理解和掌握递推算法的应用。 个人主页尘觉主页 文章目录 算法基础递推入门例题斐波那契数列费解的开关 总结 算法基础
递推
入门例题
斐波那契数列
输入一个整数 n 求斐波那契数列的第 n 项。
假定从 0 开始第 0 项为 0。
数据范围 0≤n≤39 样例 输入整数 n5
返回 5
题解
该题十分基础我们要理解斐波那契数列的组成数列中从每一项都是前两项的和所以如果不要求存下一些数的数值我们就可以直接使用几个变量操作不用进行数组创建。
class Solution {
public:int Fibonacci(int n) {if(n1)return n;if(n2) return 1;int a1,b1;int t;for(int i3;in;i){tab;ab;bt;}return t;}
};费解的开关
你玩过“拉灯”游戏吗
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关游戏者可以改变它的状态。
每一步游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯用数字 0 表示关着的灯。
下面这种状态
10111 01101 10111 10000 11011 在改变了最左上角的灯的状态后将变成
01111 11101 10111 10000 11011 再改变它正中间的灯后状态将变成
01111 11001 11001 10100 11011 给定一些游戏的初始状态编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式 第一行输入正整数 n代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组每组数据有 5 行每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式 一共输出 n 行数据每行有一个小于等于 6 的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态若 6 步以内无法使所有灯变亮则输出 −1。
数据范围 0n≤500 输入样例 3 00111 01011 10001 11010 11100
11101 11101 11110 11111 11111
01111 11111 11111 11111 11111 输出样例
3 2 -1
题解
该题我们分析可以发现我们可以通过枚举第一行的5个灯的32中开与不开的状态来实现因为第一行开关确定以后第一行的开关亮与不亮只与下一层开关有关如果i-1行j列是关的我们就开一下i行j列的灯就可以使上一个灯泡开一次递推我们就可以实现是否所有灯都能开要注意的是我们要保存一下开始的灯泡状态因为要枚举32次积累一下位运算
我们可以通过opi1表示第一行的灯是否开这是通过二进制存储实现的我们用0表示不开用1表示开。
#includecstdio
#includecstring
#includeiostream
#includealgorithmusing namespace std;
const int N510;
char g[6][6],backup[6][6];
int dx[6]{-1,0,1,0,0},dy[6]{0,1,0,-1,0};
int n;
void turn(int x,int y){for(int i0;i5;i){int axdx[i],bydy[i];if(a0||a5||b0||b5)continue;g[a][b]^1;}
}
int main(){cinn;while(n--){for(int i0;i5;i)cing[i];int ans10;for(int op0;op32;op){memcpy(backup,g,sizeof g);int stmp0;for(int i0;i5;i){if(opi1){turn(0,i);stmp;}}for(int i1;i5;i){for(int j0;j5;j){if(g[i-1][j]0){turn(i,j);stmp;}}}bool suftrue;for(int j0;j5;j){if(g[4][j]0){suffalse;break;}}if(suf){ansmin(ans,stmp);}memcpy(g,backup,sizeof backup);}if(ans6){cout-1endl;}else{coutansendl;}}return 0;
}总结
本文介绍了递推算法的基础知识并通过斐波那契数列和一个实际问题的例题进行了讲解和分析。通过学习这些例题读者可以更深入地理解递推算法的原理和应用场景为进一步探索算法和解决实际问题打下坚实的基础。
热门专栏推荐 想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集 linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
欢迎大家加入我的社区 尘觉社区 文章到这里就结束了如果有什么疑问的地方请指出诸佬们一起来评论区一起讨论 希望能和诸佬们一起努力今后我们一起观看感谢您的阅读 如果帮助到您不妨3连支持一下创造不易您们的支持是我的动力
