数据结构----算法--五大基本算法(这里没有写分支限界法)和银行家算法

数据结构----算法–五大基本算法(这里没有写分支限界法)和银行家算法

一.贪心算法

1.什么是贪心算法

在有多个选择的时候不考虑长远的情况,只考虑眼前的这一步,在眼前这一步选择当前的最好的方案

二.分治法

1.分治的概念

分治法:分而治之

将一个问题拆解成若干个解决方式完全相同的问题

满足分治的四个条件

1.问题难度随着数据规模缩小而降低

2.问题可拆分

3.子问题间相互独立

4.子问题的解可合并

2.典型的分治:二分查找(折半搜索) BinaryChop

前提:有序
时间复杂度O(log2的n次方)
1.循环实现二分查找
//循环
int BinaryChop1(int a[], int begin, int end ,int find) {if (a == nullptr || begin > end) return -1;while (begin<= end) {int mid = begin+(end- begin)/2 ;if (a[mid] == find) {cout << "找到了,返回在数组中的下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}}return -1;
}
2.递归实现二分查找
//递归
int BinaryChop2(int a[], int begin, int end, int find) {if (a == nullptr || begin > end) return -1;int mid = begin+(end- begin)/2;if (a[mid] == find) {cout << "找到了,返回数组下标" << endl;return mid;}else if (a[mid] < find) {begin = mid + 1;}else if (a[mid] > find) {end = mid - 1;}return BinaryChop2(a, begin, end, find);}

三.回溯法

1.回溯法解决的问题

1.求子集的问题

2.求排列的问题

3.求集合的问题

4.求棋盘的问题

2.回溯常见的写法

循环嵌套递归

3.用回溯法解决一道全排列的问题(此题的网址为https://leetcode.cn/problems/permutations/)

此题在之前的博客中具体分析过(博客的网址如下https://blog.csdn.net/m0_73483024/article/details/133589061?spm=1001.2014.3001.5502)

题目:

四.动态规划(Dynamic Programming)

1.动态规划可以解决的问题

动态规划可以用来求最优解(最大、最小、最多等)的问题

2.动态规划操作对象所要满足的性质

大问题可以拆解成解决方案完全相同的子问题,并且要满足以下两个性质

1.满足最优子结构性质(子问题的最优解构成当前问题的最优解)

2.无后效性(一旦某一状态被确定,那么过去这个状态如何求得的我们就再也不关注了)

3.动态规划的求解过程

1.拆分

2.定状态(子问题的最优解)

3.做决策

4.求状态转移方程

4.动态规划的实现手段

1.自顶向下带备忘的解法(大到小)

2.自底向上的解法(小到大)

注意:动态规划的空间消耗是用来换时间了

5.关于动态规划的问题

1.凑钱问题
题目:

有1元,3元,5元面额的钞票,想要凑到n元钱

解决方法:

创建一个f数组

f(n)表示想要凑到n元钱所需要的最小的钞票数

我们观察下面式子,找出规律

f(0)=0

f(1)=f(1-1)+1=1

f(2)=f(2-1)+1=2

f(3)=min{f(3-3)+1=1,f(3-1)+1=3}=1

f(4)=min{f(4-3)+1=2,f(4-1)+1=2}=2

f(5)=min{f(5-5)+1=1,f(5-3)+1=3,f(5-1)+1=3}=1

推导出动态转移方程得

f(i)=min{f(i-v[j])}+1(v[j]<=i)

这里v是一个存1元,3元,5元面额的钞票的数组,j是遍历v数组的变量

2.一维的动态划分问题:最长递增子序列(LIS)
题目:

有一个数组中有6、3、9、8、4、7、2、5、10、1这些元素,找到这个数组中的最长递增子序列

解决方法:
方法一

创建一个f数组

f(n)表示n下标与前序元素构成的LIS的长度

我们观察下面式子,找出规律

f(0)=1

f(1)=1

f(2)=max{9>3 f(1)+1=2

​ 9>6 f(0)+1=2

​ 1(只有自己本身,长度为1)

​ }=2

f(3)=max{8>3 f(1)+1=2

​ 8>6 f(0)+1=2

​ 1(只有自己本身,长度为1)

​ }=2

f(4)=max{4>3 f(1)+1=2

​ 1(只有自己本身,长度为1)

​ }=2

f(5)=max{7>4 f(4)+1=3

​ 7>3 f(1)+1=2

​ 7>6 f(0)+1=2

​ 1(只有自己本身,长度为1)

​ }=3

推导出动态转移方程得

f(i)=max(f(j)+1,1) (v[j]<v[i],0<=j<i)

这里v是数组,i和j是遍历v数组的变量

方法二(相较于方法一优化)

创建一个数组用来存等长LIS右边界的最小值(下标当作长度)

从左到右遍历数组,对创建的数组进行更新,最后数组的使用量就是最长递增子序列的长度

看下面进行理解

f(0)=1

在这里插入图片描述

f(1)=1

在这里插入图片描述

f(2)=2

在这里插入图片描述

f(3)=2

在这里插入图片描述

f(4)=2

在这里插入图片描述

f(5)=3

在这里插入图片描述

下面的过程就不再写了

方法三(在方法二的基础上,进行二分搜索,在进行数组的更新时使用二分搜索)
3.二维的动态规划问题:捡苹果
题目:

有一个m*n的格子,每个格子中有数量不一的苹果,一个小机器人(只能往右或者往下走)从左上角走到它不能再走了,求它最多能捡到多少个苹果

解决:

状态转移方程为 c[i] [j]=max{c[i-1] [j],c[i] [j-1]}+A[i] [j]

c数组存的是到每个位置所能捡到的最大苹果数量,A数组存的是每个位置的苹果数量

4.二维的动态规划问题且带附加条件的:最长公共子序列(LCS)
题目:

求X数组{A,B,B,D,C,B,C}与Y数组{B,C,D,B,A,C}的最长公共子序列

解决:

状态转移方程为 c[i] [j]={c[i-1] [j-1]+1 xi==yi

​ max{c[i-1] [j],c[i] [j-1]}} xi!=yi

​ }

c数组存的是x数组走到数组中的某个元素和y数组走到数组中的某个元素时,二者所构成的LCS的长度

c[i] [j]存的是x数组走到第i个元素,y数组走到第j个元素,二者所构成的LCS的长度

四.博弈树

1.博弈树(Game Tree)

棋类中用到的博弈树满足的条件

1.二者零和

2.全信息

3.非偶然

注意:博弈树要在时间消耗和结果准确度中做一个平衡

2.极大极小搜索树(是在原有博弈树的基础上实现的)

看下面这张图理解博弈树

甲是自己要选择尽量大的

乙是对手要使我们最小,所以乙选择尽量小的

在这里插入图片描述

3.α-β剪枝(对极大极小树的优化)

看下面图片(都是部分图,不是完整的)理解α-β剪枝

图片一

注意:这是一个深搜过程(图中数字表示处理的步骤)

在这里插入图片描述

当此图第4步得到的值小于第3步得到的值,那么第5步就不用处理了

图片二

在这里插入图片描述

注意:这是一个深搜过程(图中数字表示处理的步骤)

当此图第9步得到的值大于第7步得到的值,那么第11步和第12步就不用处理了

五.银行家算法

1.使用银行家算法要满足的条件

1.固定数量的进程共享固定数量的资源

2.进程最大请求资源数

3.单次申请的资源数不能超出可分配资源数

4.不是一次性全部申请,分批次进行

5.进程等待资源的时间是有限的(不会无休止等待)

6.当满足进程的最大资源需求,进程应该在有限时间内归还资源

2.银行家算法的操作步骤

A:总资产

B:所需的最大资源数

C:已经分配的资源数

D:仍然需要的资源数

E:每次请求的资源数

F:可分配的资源数

1.看E<=F是否满足

​ 如果不满足就等待

​ 如果满足就进行下一步

2.看E<=D是否满足

​ 如果不满足,失败

​ 如果满足就进行下一步

3.假装分配,更新各个值

​ C=C+E

​ D=D-E

​ F=F-E

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/166410.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

公有云厂商---服务对照表

各厂商特点&#xff1a; Compute: Network: Storage: Database: Migration Tool: Identify: WAF: 来源&#xff1a;https://comparecloud.in/

【网络安全 --- xss-labs靶场通关(1-10关)】详细的xss-labs靶场通关思路及技巧讲解,让你对xss漏洞的理解更深刻

靶场安装&#xff1a; 靶场安装请参考以下博客&#xff0c;既详细有提供工具&#xff1a; 【网络安全 --- xss-labs靶场】xss-labs靶场安装详细教程&#xff0c;让你巩固对xss漏洞的理解及绕过技巧和方法&#xff08;提供资源&#xff09;-CSDN博客【网络安全 --- xss-labs通…

嵌入式硬件中常见的100种硬件选型方式

1请列举您知道的电阻、电容、电感品牌&#xff08;最好包括国内、国外品牌&#xff09;。 电阻&#xff1a; 美国&#xff1a;AVX、VISHAY 威世 日本&#xff1a;KOA 兴亚、Kyocera 京瓷、muRata 村田、Panasonic 松下、ROHM 罗姆、susumu、TDK 台湾&#xff1a;LIZ 丽智、PHY…

服务器数据恢复-RAID5中磁盘被踢导致阵列崩溃的服务器数据恢复案例

服务器数据恢复环境&#xff1a; 一台3U的某品牌机架式服务器&#xff0c;Windows server操作系统&#xff0c;100块SAS硬盘组建RAID5阵列。 服务器故障&#xff1a; 服务器有一块硬盘盘的指示灯亮黄灯&#xff0c;这块盘被raid卡踢出后&#xff0c;raid阵列崩溃。 服务器数据…

JavaEE初阶学习:Servlet

1.Servlet 是什么 Servlet 是一种 Java 程序&#xff0c;用于在 Web 服务器上处理客户端请求和响应。Servlet 可以接收来自客户端&#xff08;浏览器、移动应用等&#xff09;的 HTTP 请求&#xff0c;并生成 HTML 页面或其他格式的数据&#xff0c;然后将响应发送回客户端。S…

解决CondaHTTPError HTTP 000 CONNECTION FAILED for url解决方法

解决CondaHTTPError: HTTP 000 CONNECTION FAILED for url解决方法 问题&#xff1a;使用conda install命令安装包提示CondaHTTPError: HTTP 000 CONNECTION FAILED for url 分析&#xff1a;网络连接问题&#xff0c;大概率是网速不行或者源没有换 解决方案&#xff1a;修改国…

C++多态、虚函数、纯虚函数、抽象类

多态的概念 通俗来说&#xff0c;就是多种形态&#xff0c;具体点就是去完成某个行为&#xff0c;当不同的对象去完成时会产生出不同的状态。 举个简单的例子&#xff1a;抢红包&#xff0c;我们每个人都只需要点击一下红包&#xff0c;就会抢到金额。有些人能…

5G学习笔记之5G频谱

参考&#xff1a;《5G NR通信标准》1. 5G频谱 1G和2G移动业务的频段主要在800MHz~900MHz&#xff0c;存在少数在更高或者更低频段&#xff1b;3G和4G的频段主要在450MHz ~ 6GHz&#xff1b;5G主要是410MHz ~ 6GHz&#xff0c;以及24GHz ~ 52GHz。 5G频谱跨度较大&#xff0c;可…

开源贡献难吗?

本文整理自字节跳动 Flink SQL 技术负责人李本超在 CommunityOverCode Asia 2023 上的 Keynote 演讲&#xff0c;李本超根据自己在开源社区的贡献经历&#xff0c;基于他在贡献开源社区过程中的一些小故事和思考&#xff0c;如何克服困难&#xff0c;在开源社区取得突破&#x…

Spark--经典SQL50题

目录 连接数据库准备工作 1、查询"01"课程比"02"课程成绩高的学生的信息及课程分数 2、查询"01"课程比"02"课程成绩低的学生的信息及课程分数 3、查询平均成绩大于等于60分的同学的学生编号和学生姓名和平均成绩 4、查询平均成绩…

在Kubernetes(k8s)上部署整个SpringCloud微服务应用

视频教程地址&#xff1a;https://www.bilibili.com/video/BV1Xh4y1q7aW/ 文章目录 项目准备打成使用Docker打成镜像准备Docker仓库打包项目为Docker镜像 部署应用到k8s创建nfs挂载目录创建一些基本资源创建命名空间创建拉取镜像的secret创建java运行环境的profile 部署mysql创…

Unity中Shader的XRay透视效果

文章目录 前言一、模拟菲涅尔效果1、获取 V 向量2、获取 N 向量3、点积输出效果4、模拟出菲涅尔效果(中间暗&#xff0c;周围亮) 二、实现 &#xff38;Ray 效果1、使用半透明排序、修改混合模式、加点颜色2、增加分层效果&#xff08;使用 frac 函数&#xff0c;只取小数部分&…

【深入探究Java集合框架】从List到Map的完整指南

文章目录 &#x1f31f; Java集合框架&#x1f34a; Collection&#x1f389; List&#x1f389; Set&#x1f389; Map &#x1f34a; 集合的选择&#x1f389; 1. 有序并允许重复元素的集合 List&#x1f389; 2. 无序并且不允许重复元素的集合 Set&#x1f389; 3. 维护映射…

【计网 EMail】计算机网络 EMail协议详解:中科大郑烇老师笔记 (五)

目录 0 引言1 电子邮件EMail1.1 组成1.2 SMTP协议1.3 案例&#xff1a;Alice给Bob发送报文1.4 SMTP总结1.5 邮件报文格式1.6 POP3协议和IMAP协议 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;计算机四大基础专栏&#x1f4dc; 其他章节&#xf…

辅助驾驶功能开发-功能规范篇(16)-2-领航辅助系统NAP-安全接管策略

书接上回 2.3.6安全接管策略 为保障辅助驾驶车辆的安全性,在辅助驾驶系统运行过程中,对出现的影响系统稳定性的异常情况,制定对应的安全接管策略。 异常情况可能包括:系统传感器、控制器、执行器、电源、通讯、备份系统等的故障或失效,驾驶员异常行为(如不响应车辆的接管…

毅速丨3D打印结合拓扑优化 让轻量化制造更容易

制造轻量化对于提高能源利用效率、提高产品性能和减少环境影响&#xff0c;推动制造业的绿色化、高质量发展具有重要的促进作用。 轻量化设计对许多领域都有着重要影响&#xff0c;尤其是那些需要降低能源消耗、提高运输效率或减少对环境影响的领域。如航空航天&#xff0c;轻量…

【论文阅读笔记】 Curated Pacific Northwest AI-ready Seismic Dataset

Curated Pacific Northwest AI-ready Seismic Dataset 太平洋西北部人工智能地震数据集 摘要 描述了一个AI就绪地震数据集包括各种地震事件参数 仪器元数据 地震波行描述地震目录和事件属性&#xff08;事件震级类型&#xff0c;信道类型&#xff0c;波形极性&#xff0c;信…

网络协议--ICMP:Internet控制报文协议

6.1 引言 ICMP经常被认为是IP层的一个组成部分。它传递差错报文以及其他需要注意的信息。ICMP报文通常被IP层或更高层协议&#xff08;TCP或UDP&#xff09;使用。一些ICMP报文把差错报文返回给用户进程。 ICMP报文是在IP数据报内部被传输的&#xff0c;如图6-1所示。 ICMP…

【Overload游戏引擎细节分析】Lambert材质Shader分析

一、经典光照模型&#xff1a;Phong模型 现实世界的光照是极其复杂的&#xff0c;而且会受到诸多因素的影响&#xff0c;这是以目前我们所拥有的处理能力无法模拟的。经典光照模型冯氏光照模型(Phong Lighting Model)通过单独计算光源成分得到综合光照效果&#xff0c;然后添加…

08-React扩展

08-React扩展 1. setState的2种写法 案例&#xff1a; export default class Demo extends Component {state {count: 0}add () > {// 获取当前的值const { count } this.state// 更新状态this.setState({ count: count 1 })console.log(count);}render() {const { coun…