当前位置: 首页 > 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;能够在无路由器的情况下直接、快速…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案

JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停​​ 1. ​​安全点(Safepoint)阻塞​​ ​​现象​​:JVM暂停但无GC日志,日志显示No GCs detected。​​原因​​:JVM等待所有线程进入安全点(如…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

NPOI Excel用OLE对象的形式插入文件附件以及插入图片

static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...