算法基础--递推

😀前言
递推算法在计算机科学中扮演着重要的角色。通过递推,我们可以根据已知的初始条件,通过一定的规则推导出后续的结果,从而解决各种实际问题。本文将介绍递推算法的基础知识,并通过一些入门例题来帮助读者更好地理解和掌握递推算法的应用。
🏠个人主页:尘觉主页
文章目录
- 算法基础
- 递推
- 入门例题
- 斐波那契数列
- 费解的开关
- 😄总结
算法基础
递推
入门例题
斐波那契数列
输入一个整数 n ,求斐波那契数列的第 n 项。
假定从 0 开始,第 0 项为 0。
数据范围
0≤n≤39
样例
输入整数 n=5
返回 5
题解
该题十分基础,我们要理解斐波那契数列的组成,数列中从每一项都是前两项的和,所以如果不要求存下一些数的数值,我们就可以直接使用,几个变量操作不用进行数组创建。
class Solution {
public:int Fibonacci(int n) {if(n<=1)return n;if(n==2) return 1;int a=1,b=1;int t;for(int i=3;i<=n;i++){t=a+b;a=b;b=t;}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。
数据范围
0<n≤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次,积累一下位运算>>
我们可以通过op>>i&1表示第一行的灯是否开,这是通过二进制存储实现的,我们用0表示不开,用1表示开。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>using namespace std;
const int N=510;
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 i=0;i<5;i++){int a=x+dx[i],b=y+dy[i];if(a<0||a>=5||b<0||b>=5)continue;g[a][b]^=1;}
}
int main(){cin>>n;while(n--){for(int i=0;i<5;i++)cin>>g[i];int ans=10;for(int op=0;op<32;op++){memcpy(backup,g,sizeof g);int stmp=0;for(int i=0;i<5;i++){if(op>>i&1){turn(0,i);stmp++;}}for(int i=1;i<5;i++){for(int j=0;j<5;j++){if(g[i-1][j]=='0'){turn(i,j);stmp++;}}}bool suf=true;for(int j=0;j<5;j++){if(g[4][j]=='0'){suf=false;break;}}if(suf){ans=min(ans,stmp);}memcpy(g,backup,sizeof backup);}if(ans>6){cout<<-1<<endl;}else{cout<<ans<<endl;}}return 0;
}
😄总结
本文介绍了递推算法的基础知识,并通过斐波那契数列和一个实际问题的例题进行了讲解和分析。通过学习这些例题,读者可以更深入地理解递推算法的原理和应用场景,为进一步探索算法和解决实际问题打下坚实的基础。
😁热门专栏推荐
想学习vue的可以看看这个
java基础合集
数据库合集
redis合集
nginx合集
linux合集
手写机制
微服务组件
spring_尘觉
springMVC
mybits
等等等还有许多优秀的合集在主页等着大家的光顾感谢大家的支持
🤔欢迎大家加入我的社区 尘觉社区
文章到这里就结束了,如果有什么疑问的地方请指出,诸佬们一起来评论区一起讨论😁
希望能和诸佬们一起努力,今后我们一起观看感谢您的阅读🍻
如果帮助到您不妨3连支持一下,创造不易您们的支持是我的动力🤞

相关文章:
算法基础--递推
😀前言 递推算法在计算机科学中扮演着重要的角色。通过递推,我们可以根据已知的初始条件,通过一定的规则推导出后续的结果,从而解决各种实际问题。本文将介绍递推算法的基础知识,并通过一些入门例题来帮助读者更好地理…...
超市销售数据-python数据分析项目
Python数据分析项目-基于Python的销售数据分析项目 文章目录 Python数据分析项目-基于Python的销售数据分析项目项目介绍数据分析结果导出数据查阅 数据分析内容哪些类别比较畅销?哪些商品比较畅销?不同门店的销售额占比哪个时间段是超市的客流高封期?查看源数据类型计算本月…...
java实现手机号,密码,游邮箱 , 验证码的正则匹配工具类
先定义一个抽象类RegexPatterns,定义相关正则字符串 : public abstract class RegexPatterns {/*** 手机号正则*/public static final String PHONE_REGEX "^1([38][0-9]|4[579]|5[0-3,5-9]|6[6]|7[0135678]|9[89])\\d{8}$";/*** 邮箱正则*/public stat…...
java中的Arrays类的常用操作
Arrays类位于 java.util 包中,主要包含了操作数组的各种方法。 import java.util.Arrays; Arrays.sort(arr); int index Arrays.binarySearch(arr, 3); boolean isEqual Arrays.equals(arr1, arr2); // isEqual为true int[] arrnew int[5]; Arrays.fill(arr, 7)…...
回溯算法|78.子集
力扣题目链接 class Solution { private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex) {result.push_back(path); // 收集子集,要放在终止添加的上面,否则会漏掉自…...
VC++、GCC、CLANG,INT128有符号整数编译器关键字
注意INT128为目标平台扩展关键字,不属于C/C语言本身支持特性,每个C/C编译器平台支持上都略有不同,甚至不支持。 可以详细参考本人此篇文章: GUN C/C (GCC/CLANG) 对于 __int128_t (128位有符号大整数的扩展支持平台限…...
用于HUD平视显示器的控制芯片:S2D13V40
一款利用汽车抬头显示技术用于HUD平视显示器的控制芯片:S2D13V40。HUD的全称是Head Up Display,即平视显示器,以前应用于军用飞机上,旨在降低飞行员需要低头查看仪表的频率。起初,HUD通过光学原理,将驾驶相关的信息投射…...
JSP使用模板字符串数据不能渲染的问题
entrap father 的 rubbish JSP 数据不能直接渲染,要从接口请求后去拼接结构 然后模板字符串不能直接用 用以下方法是不能渲染出数据的 let div <div class"circulation"><div class"list"><div class"left"><div class&qu…...
AI音乐GPT时刻来临:Suno 快速入门手册!
✨✨ 欢迎大家来访Srlua的博文(づ ̄3 ̄)づ╭❤~✨✨ 🌟🌟 欢迎各位亲爱的读者,感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢,在这里我会分享我的知识和经验。&am…...
数字乡村发展蓝图:科技赋能农村实现全面振兴
目录 一、数字乡村发展蓝图的内涵与目标 二、科技赋能农村:数字乡村发展的动力与路径 (一)加强农业科技创新,提升农业生产效率 (二)推进农村电商发展,拓宽农民增收渠道 (三&…...
Day42 动态规划 part04
Day42 动态规划 part04 46. 携带研究材料(卡哥的卡码网的题目) 背包问题 我的思路: 写不了一点儿…T^T 总结规律就是,dp数组要比原来各个size 1,dp[i][j] Math.max(xxx, xxxx(根据题目情况进行各种处理)) 解答: …...
python set是什么类型
python set是一种数据类型,数学里的集合概念,在Python语言里对应的是set类型。与list,tuple不同的地方是,set更加强调的是一种“从属关系”(membership),跟顺序无关,所以有重复的元素…...
redis事务(redis features)
redis支持事务,也就是可以在一次请求中执行多个命令。redis中的事务主要是通过MULTI和EXEC这两个命令来实现的。 MULTI命令用来开启一个事务,事务开启之后,所有的命令就都会被放入到一个队列中,最后通过一个EXEC命令来执行事务中…...
SpringBoot整合minio
SpringBoot整合minio 1. 下载及安装1.1 windows版本1.2 Linux版本 2. SpringBoot整合minio2.1 依赖2.2 配置文件2.3 配置类2.4 工具类2.5 测试1. 业务层2. 控制层 1. 下载及安装 1.1 windows版本 目录结构 启动文件 标红的地方按实际安装地更改 echo off REM 声明采用UT…...
3090. 每个字符最多出现两次的最长子字符串
说在前面 🎈不知道大家对于算法的学习是一个怎样的心态呢?为了面试还是因为兴趣?不管是出于什么原因,算法学习需要持续保持。 题目描述 给你一个字符串 s ,请找出满足每个字符最多出现两次的最长子字符串,…...
26.活锁、饥饿锁
两个线程,相互改变了对方结束条件,导致两个线程不能结束。执行时间也都是一样,导致两个线程永远不会结束。 Slf4j public class LiveLockDemo {static volatile int count 10;public static void main(String[] args) {new Thread(() ->…...
docker 安装nginx
一、先查看有没有nginx镜像 docker images 二、发现没有nginx镜像,下载最新镜像 docker pull nginx 三、运行镜像 为了先复制出部分文件,先启动一个临时容器 docker run --name nginx -p 9001:80 -d nginx docker cp nginx:/etc/nginx/conf.d /home/…...
2024年阿里云新用户便宜购买云服务器攻略:5大细节助你降低购买成本
随着互联网的蓬勃发展,无论是个人还是企业,拥有一个稳定且高效的网站或APP已成为提升竞争力的关键。为了将这些项目部署并运行起来,购买一台实用又便宜的云服务器是必不可少的。阿里云作为国内首屈一指的云服务提供商,自然成为了众…...
SSTI模板注入(jinja2)
前面学习了SSTI中的smarty类型,今天学习了Jinja2,两种类型都是flask框架的,但是在注入的语法上还是有不同 SSTI:服务器端模板注入,也属于一种注入类型。与sql注入类似,也是通过凭借进行命令的执行ÿ…...
ESP32学习---ESP-NOW(一)
ESP32学习---ESP-NOW(一) 官网简介arduino 官网简介 首先看官网的介绍:https://www.espressif.com.cn/zh-hans/solutions/low-power-solutions/esp-now ESP-NOW 是乐鑫定义的一种无线通信协议,能够在无路由器的情况下直接、快速…...
HTML 列表、表格、表单
1 列表标签 作用:布局内容排列整齐的区域 列表分类:无序列表、有序列表、定义列表。 例如: 1.1 无序列表 标签:ul 嵌套 li,ul是无序列表,li是列表条目。 注意事项: ul 标签里面只能包裹 li…...
cf2117E
原题链接:https://codeforces.com/contest/2117/problem/E 题目背景: 给定两个数组a,b,可以执行多次以下操作:选择 i (1 < i < n - 1),并设置 或,也可以在执行上述操作前执行一次删除任意 和 。求…...
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数
高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
适应性Java用于现代 API:REST、GraphQL 和事件驱动
在快速发展的软件开发领域,REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名,不断适应这些现代范式的需求。随着不断发展的生态系统,Java 在现代 API 方…...
关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...
[拓扑优化] 1.概述
常见的拓扑优化方法有:均匀化法、变密度法、渐进结构优化法、水平集法、移动可变形组件法等。 常见的数值计算方法有:有限元法、有限差分法、边界元法、离散元法、无网格法、扩展有限元法、等几何分析等。 将上述数值计算方法与拓扑优化方法结合&#…...
Selenium 查找页面元素的方式
Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素,以下是主要的定位方式: 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...
二叉树-144.二叉树的前序遍历-力扣(LeetCode)
一、题目解析 对于递归方法的前序遍历十分简单,但对于一位合格的程序猿而言,需要掌握将递归转化为非递归的能力,毕竟递归调用的时候会调用大量的栈帧,存在栈溢出风险。 二、算法原理 递归调用本质是系统建立栈帧,而非…...
