Chen0495的空间站

¶算法思想 ¶暴力优化 给定主串S和模式串P: S:BBC ABCDAB ABCDABCDABDE P:ABCDABD 暴力算法就是一个一个地匹配,失配了就模式串P整体后移一位,从头开始与主串S的失配字符的下一个字符开始匹配. 如图: 暴力算法做了太多无用功,如下图所示: D与空格失配后,失配字符前的ABCDAB字串显然是配对的,换言之我们已经知道失配字符前的所有字符,那我们可以根据这些已知字符来跳过一些不可能的情况. 如上图,失配字符D之前的字串ABCDAB具有相同且最大的前后缀AB,故我们可以直接跳转使得失配字符前的字串的前缀(即模式串的前缀)与后缀(即主串的后缀)相对应. 也就是说,我们从头到尾假设每个字符失配,得到失配字符前的字串中相同的前缀和后缀,并记录下来,即可省略一大批步骤.那么怎么得到这个相同前后缀呢? ¶KMP步骤 寻找前后缀最长公共元素长度 对于字串P = P[0] P[1] P[2] ... P[j-1] P[j],找其最长公共前后缀. 如果有P[0] P[1] ... P[k] = P[j-k] P[j-k+1] ... P[j]即某条公共前后缀,那么 ...

¶可分离变量方程 例1: 例2: ¶齐次方程 例1: 例2: ¶一阶齐次线性方程&一阶非齐次线性方程 例1,例2: 例3: 例4:

¶背景 中缀表达式,运算符在操作数的中间,即一般的表达式; 后缀表达式,运算符在操作数的后面; 前缀表达式,运算符在操作数之前. 下面我们实现由一般的中缀表达式到后缀表达式的转换. ¶手算 举例说明: a+b*c+(d*e+f)*g 将其按照先乘除后加减以及从左到右的原则添加上括号((a + (b * c)) + (((d * e) + f) * g)),熟练了该步可以省去,添加括号反而增加麻烦. 根据括号由内向外将表达式转换为后缀形式a bc* + de* f+ g* +. 得到最终结果,但此法不适用于计算机. 但我们可以从中看出一些规律,这对设计计算机算法有所裨益. 例如: 操作数之间的相对顺序并未改变. 内层的运算符总是比外层的运算符先输出. a+b*c中*要先运算;而a*b+c...中也是*先运算,但到+时意味着前面的运算已经影响不到后面的运算了(除非有括号),也就是说在没有括号参与的情况下,低运算级(+,-)前面的高运算级(+,-,*,/)可以输出了. 接上条,在括号内部的运算总是优先的,于是我们可以将右括号)视为一个括号运算的结束,那么怎么找到与之对应的左括号呢?我 ...

¶背景 卡特兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡特兰（1814–1894）命名。历史上，清朝数学家明安图（1692年－1763年）在其《割圜密率捷法》中最先发明这种计数方式，远远早于卡特兰。有中国学者建议将此数命名为“明安图数” 或“明安图-卡特兰数”。-- by Wikipedia 其一般公式为: ¶问题 n个不同元素依次入栈,问有多少种合法的出栈顺序? ¶思路 有A、B两个元素,入栈顺序AB,则出栈情况有两种: 入A, 出A, 入B, 出B. 入A, 入B, 出B, 出A. 现在假设f(n)为 " n 个不同元素依次入栈, 出栈顺序的种类数". 显然f(1)=1,f(2)=2. 现在按照第一个入栈元素,在出栈序列中的位置进行分类讨论, 假设入栈序列ABCD: A第一个出栈时,A先进,然后马上出栈.这种情况下,共有“BCD出栈顺序的种类数”种方案.也就是f(n-1)种. A第二个出栈时,A先进,B再进,之后B需要马上出来(这样才能确保A排第二),此时共有f(n-2)种方案. A第三个出栈时,A先进,之后只要确保排 ...

¶深搜 例: 求1到n这n个数的全排列 如图: 相当于前序遍历根 -> 左 -> 右的顺序,将一个子树遍历到底再回溯. 注意回溯需要保存和还原现场!!! 即12_ -> 123操作完成之后从子节点回溯到父节点需要还原现场:123 -> 12_. 用栈. 代码之后补… ¶广搜 ¶参考 🔗DFS (弱弱 =》 深搜 =》神搜 =》大佬)🔗

¶正文 简单介绍下迪杰斯特拉算法,一般用于寻找最短路. 如图1到6的最短路是: 1 -> 2 -> 3 -> 5 -> 6 注意到在最短路径中,起点到中间节点比如 1 -> 3 的最短路仍然包含在整个最短路径中 1 -> 2 -> 3,这很容易验证,如果起点到中间点有 更短的路径,那么起点到终点最短路径就不是上面那一条了,显然矛盾. 基于上述思想,我们可以找到一条从起点到终点的路径(最短路径),其起点到每一个中间节点的距离依然是这两者的最短距 离,于是我们只需要找到离当前节点最近的节点作为当前路径的下一个目的地,直到到达终点或者遍历完所有可到达点为止. 基本流程: 建立存储矩阵,存放点到点的距离,初值默认无穷大: 创建最短距离数组,存放起始点到各个点的距离,初值默认无穷大: 创建标记数组,标记该点是否已访问,初值默认False. 标记起点. 从起点开始,访问离起点最近的值(此处为2)并标记,更改最短距离数组中节点2的值. 找离 2 最近的点(此处为4),访问并标记,更改最短距离数组中节点4的值. … 到达终点或遍历完所有可到达节 ...

总而言之就是 2筛出4;# ×2 2,3筛出6,9;# ×3 2,3筛出8;# ×4,4%2==0,直接跳出,故不计3×4=12,又因为2是4的最小素因子,所以4*3=(2*2)*3=2*(2*3)=2*6=12,即12会被6筛出,此处不需要多此一举 2,3,5筛出10,15,25;# ×5 2,3,5筛出12,18,30;# ×6,同理,6%2==3,后面的3,5不需要算了,因为6*5=(2*3)*5=2*(3*5)=2*15=30被15筛出,此处若计算3,5将多出大量无用计算 是否跳过多余计算比较: Code: 1234567891011121314151617181920212223242526# -*-coding:utf-8-*-maxl = 1000000 # 筛选范围count = 0 ss = [] # 素数check = [] # 0代表素数，1代表合数。全部初始化为素数。for x in range(0, maxl+1): check.append(0)# 筛选出 2~10^6 所有素数for i in range(2, maxl): # ...

¶第一章 - 分布式计算概述 分布式计算、并行计算的概念 分布式计算指在☞分布式系统上运行的计算, 它是将一个大型计算任务分成很多部分分别交给其他的计算机处理, 并将所有的计算结果合并为原问题的一种计算方式. 并行计算是指同时使用多种计算资源解决计算问题的过程，是提高计算机系统计算速度和处理能力的一种有效手段。它的基本思想是用多个处理器来协同求解同一问题，即将被求解的问题分解成若干个部分，各部分均由一个独立的处理机来并行计算. 一个典型的分布式系统构成 分布式系统的特征 CAP理论 [{"url":"https://img.chen0495.top/img/20201223152128.png","alt":""},{"url":"https://img.chen0495.top/img/20201223152105.png","alt":""},{"url":"https://img.chen0495.top/img/20201225124623.png","alt":""}] 加载更多 分布式计算的核心技术 ...

¶介绍[^1] 银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。 它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。 ¶背景[^1] 在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。 银行家在客户申请的贷款数量不超过自己拥有的最大值时，都应尽量满足客户的需要。在这样的描述中，银行家就好比操作系统，资金就是资源，客户就相当于要申请资源的进程。 ¶算法 对于如图的资源分配表: Allocation(已经分配出去的资源), MAX(最多需要多少资源), Available(空闲资源) 首先计算出Need (Need = MAX - Allocation), 即还需要多少资源: 然后加一个全为False的字段(FINISH, 表示当前进程是否满足, 也可以不加,记着就行): 接下来找到 Need 比 Available 小的(即空闲资源可以满足当前进程所需): P ...

¶习题 老师给的题库，ps是私货, 可看可不看… ¶第一章 - 引论 ¶名词解释 操作系统: 操作系统是管理和控制计算机系统内各种硬件和软件资源,有效地组织多道程序运行的系统软件（或程序集合）,是用户与计算机之间的接口。 管控软硬件,组织多道运行,人机接口 管态: 执行操作系统程序时,处理机所处的状态. 目态: 执行普通用户程序时,处理机所处的状态. 多道程序设计: 在该设计技术下, 内存中能够同时存放多道程序, 在管理程序的控制下交替执行. 这些作业共享CPU和系统其他资源. 多道、交替、共享 并发: 是指两个或多个活动在同一给定的时间间隔中进行。它是宏观上的概念。 ps: 非同时刻运行. 并行: 是指两个或多个活动在同一时刻同时执行的情况。 吞吐量: 在一段给定的时间内，计算机所能完成的总工作量。 分时: 就是对时间的共享。在分时系统中，分时主要是指若干并发程序对CPU时间的共享。 实时: 表示“及时”或“既时”。 ps: 不重要… 系统调用: 是用户在程序中能以函数调用形式调用的、由操作系统提供的子功能的集合。每一个子功能称作一条系统调用命令。它是操作系统对外的 ...