当前位置: 首页 > news >正文

算法基础--递推

img

😀前言
递推算法在计算机科学中扮演着重要的角色。通过递推,我们可以根据已知的初始条件,通过一定的规则推导出后续的结果,从而解决各种实际问题。本文将介绍递推算法的基础知识,并通过一些入门例题来帮助读者更好地理解和掌握递推算法的应用。

🏠个人主页:尘觉主页

文章目录

  • 算法基础
    • 递推
      • 入门例题
        • 斐波那契数列
        • 费解的开关
    • 😄总结

算法基础

递推

入门例题

斐波那契数列

输入一个整数 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连支持一下,创造不易您们的支持是我的动力🤞

img

相关文章:

算法基础--递推

&#x1f600;前言 递推算法在计算机科学中扮演着重要的角色。通过递推&#xff0c;我们可以根据已知的初始条件&#xff0c;通过一定的规则推导出后续的结果&#xff0c;从而解决各种实际问题。本文将介绍递推算法的基础知识&#xff0c;并通过一些入门例题来帮助读者更好地理…...

超市销售数据-python数据分析项目

Python数据分析项目-基于Python的销售数据分析项目 文章目录 Python数据分析项目-基于Python的销售数据分析项目项目介绍数据分析结果导出数据查阅 数据分析内容哪些类别比较畅销?哪些商品比较畅销?不同门店的销售额占比哪个时间段是超市的客流高封期?查看源数据类型计算本月…...

java实现手机号,密码,游邮箱 , 验证码的正则匹配工具类

先定义一个抽象类RegexPatterns&#xff0c;定义相关正则字符串 : 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 包中&#xff0c;主要包含了操作数组的各种方法。 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); // 收集子集&#xff0c;要放在终止添加的上面&#xff0c;否则会漏掉自…...

VC++、GCC、CLANG,INT128有符号整数编译器关键字

注意INT128为目标平台扩展关键字&#xff0c;不属于C/C语言本身支持特性&#xff0c;每个C/C编译器平台支持上都略有不同&#xff0c;甚至不支持。 可以详细参考本人此篇文章&#xff1a; GUN C/C (GCC/CLANG) 对于 __int128_t &#xff08;128位有符号大整数的扩展支持平台限…...

用于HUD平视显示器的控制芯片:S2D13V40

一款利用汽车抬头显示技术用于HUD平视显示器的控制芯片:S2D13V40。HUD的全称是Head Up Display&#xff0c;即平视显示器&#xff0c;以前应用于军用飞机上&#xff0c;旨在降低飞行员需要低头查看仪表的频率。起初&#xff0c;HUD通过光学原理&#xff0c;将驾驶相关的信息投射…...

JSP使用模板字符串数据不能渲染的问题

entrap father 的 rubbish JSP 数据不能直接渲染,要从接口请求后去拼接结构 然后模板字符串不能直接用 用以下方法是不能渲染出数据的 let div <div class"circulation"><div class"list"><div class"left"><div class&qu…...

AI音乐GPT时刻来临:Suno 快速入门手册!

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…...

数字乡村发展蓝图:科技赋能农村实现全面振兴

目录 一、数字乡村发展蓝图的内涵与目标 二、科技赋能农村&#xff1a;数字乡村发展的动力与路径 &#xff08;一&#xff09;加强农业科技创新&#xff0c;提升农业生产效率 &#xff08;二&#xff09;推进农村电商发展&#xff0c;拓宽农民增收渠道 &#xff08;三&…...

Day42 动态规划 part04

Day42 动态规划 part04 46. 携带研究材料(卡哥的卡码网的题目) 背包问题 我的思路: 写不了一点儿…T^T 总结规律就是&#xff0c;dp数组要比原来各个size 1&#xff0c;dp[i][j] Math.max(xxx, xxxx&#xff08;根据题目情况进行各种处理&#xff09;) 解答&#xff1a; …...

python set是什么类型

python set是一种数据类型&#xff0c;数学里的集合概念&#xff0c;在Python语言里对应的是set类型。与list&#xff0c;tuple不同的地方是&#xff0c;set更加强调的是一种“从属关系”&#xff08;membership&#xff09;&#xff0c;跟顺序无关&#xff0c;所以有重复的元素…...

redis事务(redis features)

redis支持事务&#xff0c;也就是可以在一次请求中执行多个命令。redis中的事务主要是通过MULTI和EXEC这两个命令来实现的。 MULTI命令用来开启一个事务&#xff0c;事务开启之后&#xff0c;所有的命令就都会被放入到一个队列中&#xff0c;最后通过一个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. 每个字符最多出现两次的最长子字符串

说在前面 &#x1f388;不知道大家对于算法的学习是一个怎样的心态呢&#xff1f;为了面试还是因为兴趣&#xff1f;不管是出于什么原因&#xff0c;算法学习需要持续保持。 题目描述 给你一个字符串 s &#xff0c;请找出满足每个字符最多出现两次的最长子字符串&#xff0c;…...

26.活锁、饥饿锁

两个线程&#xff0c;相互改变了对方结束条件&#xff0c;导致两个线程不能结束。执行时间也都是一样&#xff0c;导致两个线程永远不会结束。 Slf4j public class LiveLockDemo {static volatile int count 10;public static void main(String[] args) {new Thread(() ->…...

docker 安装nginx

一、先查看有没有nginx镜像 docker images 二、发现没有nginx镜像&#xff0c;下载最新镜像 docker pull nginx 三、运行镜像 为了先复制出部分文件&#xff0c;先启动一个临时容器 docker run --name nginx -p 9001:80 -d nginx docker cp nginx:/etc/nginx/conf.d /home/…...

2024年阿里云新用户便宜购买云服务器攻略:5大细节助你降低购买成本

随着互联网的蓬勃发展&#xff0c;无论是个人还是企业&#xff0c;拥有一个稳定且高效的网站或APP已成为提升竞争力的关键。为了将这些项目部署并运行起来&#xff0c;购买一台实用又便宜的云服务器是必不可少的。阿里云作为国内首屈一指的云服务提供商&#xff0c;自然成为了众…...

SSTI模板注入(jinja2)

前面学习了SSTI中的smarty类型&#xff0c;今天学习了Jinja2&#xff0c;两种类型都是flask框架的&#xff0c;但是在注入的语法上还是有不同 SSTI&#xff1a;服务器端模板注入&#xff0c;也属于一种注入类型。与sql注入类似&#xff0c;也是通过凭借进行命令的执行&#xff…...

ESP32学习---ESP-NOW(一)

ESP32学习---ESP-NOW&#xff08;一&#xff09; 官网简介arduino 官网简介 首先看官网的介绍&#xff1a;https://www.espressif.com.cn/zh-hans/solutions/low-power-solutions/esp-now ESP-NOW 是乐鑫定义的一种无线通信协议&#xff0c;能够在无路由器的情况下直接、快速…...

C++_核心编程_多态案例二-制作饮品

#include <iostream> #include <string> using namespace std;/*制作饮品的大致流程为&#xff1a;煮水 - 冲泡 - 倒入杯中 - 加入辅料 利用多态技术实现本案例&#xff0c;提供抽象制作饮品基类&#xff0c;提供子类制作咖啡和茶叶*//*基类*/ class AbstractDr…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

Cesium1.95中高性能加载1500个点

一、基本方式&#xff1a; 图标使用.png比.svg性能要好 <template><div id"cesiumContainer"></div><div class"toolbar"><button id"resetButton">重新生成点</button><span id"countDisplay&qu…...

聊聊 Pulsar:Producer 源码解析

一、前言 Apache Pulsar 是一个企业级的开源分布式消息传递平台&#xff0c;以其高性能、可扩展性和存储计算分离架构在消息队列和流处理领域独树一帜。在 Pulsar 的核心架构中&#xff0c;Producer&#xff08;生产者&#xff09; 是连接客户端应用与消息队列的第一步。生产者…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...