【算法笔记】递归与回溯
递归与回溯
To Iterate is Human, to Recurse, Divine.
—L. Peter Deutsch
人理解迭代,神理解递归。
—L. Peter Deutsch
1.什么是递归呢
递归形象描述:
你打开面前这扇门,看到屋里面还有一扇门。
你走过去,发现手中的钥匙还可以打开它,你推开门,发现里面还有一扇门,你继续打开它。
若干次之后,你打开面前的门后,发现只有一间屋子,没有门了。
然后,你开始原路返回,每走回一间屋子,你数一次,走到入口的时候,
你可以回答出你到底用这你把钥匙打开了几扇门。
2.递归算法(Recursion)
- 定义:直接或间接地出现对自身的调用。
- 本质:递归即递进与回归,基本思想就是把规模大的问题转化为规模小的相似的子问题来解决。但必须有一个明确的结束条件(递归出口)
//斐波那契
int f(int n)
{if(n==1)return 1;else if(n==2)return 1;elsereturn f(n-1)+f(n-2);
}
利用递归完成的题目特点:
- 可以将当前问题转换成规模更小的问题,且新问题和原问题解法完全相同
- 有一个明确的递归边界
3.递归案例
**用递归方法求:**1+2+3+……+n=
递归关系:
f(n)=f(n-1)+n; 递归关系
f(1)=1; 递归出口
用递归方法求:n!
递归关系:
f(n)=f(n-1)*n; 递归关系
f(1)=1; 递归出口
4.例题
王小二切饼
题目描述:
王小二自夸刀工不错,有人放一张大的煎饼在砧板上,问他:“饼不许离开砧板,切n(1<=n<=100)刀最多能分成几块?
输入格式:
输入切的刀数n
输出格式:
输出切n刀最多切的块数
输入样例:
3
输出样例:
7
解题思路
杨辉三角
AC代码:
#include<bits/stdc++.h>
using namespace std;
int f(int x,int y)
{printf("调用f(%d,%d)\n",x,y);if(x==y || y==1)return 1;return f(x-1,y-1)+f(x-1,y);
}
int main()
{int m,n;cin>>m>>n;cout<<f(m,n);return 0;
}
5.程序分析
6.【背】核心代码(模板)
递归模板:
void recursion(大规模){if(end_condition){ //递归出口……return;}else{recursion(小规模); //递进,将大规模转换为小规模solve; //回归}
}
7.总结
- 递归就是函数自己调用自己
- 在递归过程中,必须有一个明确的递归结束条件,即递归出口
- 每一次的函数调用都有自己的变量。
- 每一次函数调用都会有一次返回。
- 递归函数中,位于递归调用前的语句和各级被调用函数具有相同的执行顺序。
- 递归函数中,位于递归调用后的语句和各个被调用函数的顺序相反。
优缺点:
**优点:**实现简单,可读性好;
**缺点:**递归调用,占用空间大;递归太深,易发生栈溢出;可能会出现重复计算的问题(重叠子问题)
相关文章:

【算法笔记】递归与回溯
递归与回溯 To Iterate is Human, to Recurse, Divine. —L. Peter Deutsch 人理解迭代,神理解递归。 —L. Peter Deutsch 1.什么是递归呢 递归形象描述: 你打开面前这扇门,看到屋里面还有一扇门。 你走过去,发现手中的钥匙还可以…...

蓝桥杯备赛——Echarts学习
文章目录前言学习 ECharts 的方法快速上手基础知识option 配置选项可选配置title 标题组件tooltip 提示框组件axisPointer 坐标轴指示器legend 图例组件toolbox 工具栏坐标轴xAxis和yAxisseries ([ ]用数组表示,数组里是一个个数据对象)饼状图散点图交互…...
动态规划--最长公共子串
最长公共子串公共子串问题费曼算法动态规划算法思路代码实现公共子串问题 在计算机科学中,最长公共子串问题是寻找两个或多个已知字符串最长的子串。此问题与最长公共子序列问题的区别在于子序列不必是连续的,而子串却必须是。链接: 百度百科 费曼算法…...

【运筹优化】剩余空间法求解带顺序约束的二维矩形装箱问题 + Java代码实现
文章目录一、带顺序约束的二维矩形装箱问题二、剩余空间法三、完整代码实现3.1 Instance 实例类3.2 Item 物品类3.3 PlaceItem 已放置物品类3.4 Solution 结果类3.5 RSPackingWithWeight 剩余空间算法类3.6 Run 运行类3.7 测试案例3.8 ReadDataUtil 数据读取类3.9 运行结果展示…...

第四阶段15-关于权限,处理解析JWT时的异常,跨域请求,关于Spring Security的认证流程
处理解析JWT时的异常 由于解析JWT是在过滤器中执行的,而过滤器是整个服务器端中最早接收到所有请求的组件,此时,控制器等其它组件尚未运行,则不可以使用此前的“全局异常处理器”来处理解析JWT时的异常(全局异常处理器…...

毕业设计 基于51单片机的指纹红外密码电子锁
基于51单片机的指纹红外密码电子锁1、项目简介1.1 系统框架1.2 系统功能2、部分电路设计2.1 STC89C52单片机最小系统电路设计2.2 矩阵按键电路电路设计2.3 液晶显示模块电路设计3、部分代码展示3.1 LCD12864显示字符串3.2 串口初始化实物图1、项目简介 选题指导,项…...

【JavaWeb】数据链路层协议——以太网 + 应用层协议——DNS
以太网 以太网不是一个具体的网络,而是一个技术标准,主要应用于数据链路层和物理层。 以太网数据帧结构 以太网的数据帧结构由三部分构成: 帧头 载荷 帧尾 其中的MAC地址是六位,这样就比IPV4所表示的地址大很多,…...
docker 容器安装 python jre
Dockerfile FROM python:2.7.11-alpine RUN mkdir /usr/local/java WORKDIR /usr/local/java # 5.更改 Alpine 的软件源为阿里云,默认从官方源拉取比较慢 RUN echo http://mirrors.aliyun.com/alpine/v3.10/main/ > /etc/apk/repositories && \ echo…...
Linux下将C++程序打包成动态库静态库方法
之前在这篇文章里介绍过动态库和静态库的理论部分,这篇文章主要介绍下实际的操作步骤: 静态链接库生成 gcc -c main.cpp -o main.o ar -rc libmain.a main.o sudo cp libmain.a /usr/local/lib 调用即可解释一下上面的命令:前两步生成了libmain.a sudo…...

Centos7 服务器基线检查处理汇总
1、服务器超时设置 问题描叙 TMOUT的值大于key2且小于等于{key2}且小于等于key2且小于等于{key1}视为合规 查看命令:export检测结果 超时时间:0处理方式 备份/etc/profile文件 cp /etc/profile /etc/profile_bak编辑profile文件 vim /etc/profile修改/新增 TMO…...

PaddleOCR遇到 lanms-neo问题处理
在window环境中安装PaddleOCR依赖是真的蛋疼,关键官方论坛里也都没有具体的解决方案。吐槽。。。吐槽。。。 我在 “windows安装lanms-neo问题处理”文章中看到lanms-neo问题全过程解决。个人觉得文档说明不是很细致,导致我按步骤执行,还是安…...

coreldraw2023安装包下载及新功能介绍
对于广告标识业来说 coreldraw这个软件,对我们来说绝对不陌生,我从2008年开始接触到广告制作,到现在已经13多年了,从一开始的coreldraw 9红色的热气球开始。就被这个强大的软件所吸引,他有强大的排榜功能已经对位图的处…...

Nginx 负载均衡服务失败场景
nginx可以配置负载均衡,我们可以通过配置实现nginx负载均衡。这里部署了两个服务producter-one和producter-one2。 upstream proxyproducter-one {server producter-one:8080 weight1;server producter-one2:8080 weight1;}# 访问其他服务server {listen 9090…...

开学季哪个电容笔好?2023口碑最好电容笔推荐
虽说苹果原装的电容笔非常好用,性能也非常不错,但由于价格昂贵,普通的学生是没办法购买的,再加上重量比较大,使用时间长了,难免会让人感觉到疲劳。如果仅仅是为了学习记笔记,那就没必要再去购买…...
经验分享-如何使用http调用chatGPT-3.5-turbo模型API
今天上午,就在工作群里收到了关于openAI发布chatGPT官方模型的消息分享。openAI这次的动作真的很快啊,没想到这么快就直接发布了chatGPT目前所使用的模型api。据Open AI在官方消息,本次开放了ChatGPT和Whisper的模型API,可以供用户…...
【C#】yyyy-MM-dd HH:mm:ss 时间格式 时间戳 全面解读超详细
C# 日期转字符串 实例化一个时间字符串 DateTimeFormatInfo dfInfonew DateTimeFormatInfo(); dfInfo.ShortDatePattern "yyyy/MM/dd hh:mm:ss:ffff"; DateTime dt Convert.ToDateTime("2019/07/01 18:18:18:1818", dfInfo);日期转字符串 string dat…...

基于神经网络的滑模鲁棒控制
目录 前言 1.双关节机械手臂模型 2.神经网络自适应律设计 3. 滑模控制律设计 4. 仿真分析 4.1 仿真模型 4.2 仿真结果 4.3 小结 5 学习问题 前言 上一篇文章我介绍了神经网络补偿的机理,只不过控制律不同,本章我们结合滑模理论设计控制律&#…...

2023年融资融券研究报告
第一章 行业概况 融资融券是证券交易市场上的两种金融衍生品交易方式,主要用于股票、债券等证券的融资和投资。 融资是指投资者向证券公司借入资金购买证券,以期望股票价格上涨后卖出获得利润。融资需支付一定的利息和费用,利息根据借入的资…...

Nodejs环境配置 | Linux安装nvm | windows安装nvm
文章目录一. 前言二. Linux Nodejs环境配置1. 安装nvm2. 配置npm三. Windows Nodejs环境配置1. 安装nvm2. 配置npm四. nvm基本使用一. 前言 由于在实际开发中一些不同的项目需要不同的npm版本来启动,所以本篇文章会基于nvm这个node版本管理工具来进行Linux和Winodw…...

显示接口测试
背景需求两个显示器连接到一台PC,期望每台显示器可以单独显示,在一台显示器显示时,另外一台显示器同PC的连接断开,即系统下查看到连接状态为disconnected。同时在显示器上图形化显示当前显示器编号。如下图,期望当显示…...
Linux简单的操作
ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
docker 部署发现spring.profiles.active 问题
报错: org.springframework.boot.context.config.InvalidConfigDataPropertyException: Property spring.profiles.active imported from location class path resource [application-test.yml] is invalid in a profile specific resource [origin: class path re…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...

ui框架-文件列表展示
ui框架-文件列表展示 介绍 UI框架的文件列表展示组件,可以展示文件夹,支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项,适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

QT开发技术【ffmpeg + QAudioOutput】音乐播放器
一、 介绍 使用ffmpeg 4.2.2 在数字化浪潮席卷全球的当下,音视频内容犹如璀璨繁星,点亮了人们的生活与工作。从短视频平台上令人捧腹的搞笑视频,到在线课堂中知识渊博的专家授课,再到影视平台上扣人心弦的高清大片,音…...

运行vue项目报错 errors and 0 warnings potentially fixable with the `--fix` option.
报错 找到package.json文件 找到这个修改成 "lint": "eslint --fix --ext .js,.vue src" 为elsint有配置结尾换行符,最后运行:npm run lint --fix...

免费批量Markdown转Word工具
免费批量Markdown转Word工具 一款简单易用的批量Markdown文档转换工具,支持将多个Markdown文件一键转换为Word文档。完全免费,无需安装,解压即用! 官方网站 访问官方展示页面了解更多信息:http://mutou888.com/pro…...