服装网站建设方案摘要,海力建设集团有限公司网站,自适应网页设计尺寸,河北邢台区号算法进阶视频地址#xff1a;https://www.bilibili.com/video/BV1uA411N7c5
1. 贪心算法
贪心算法#xff08;又称贪婪算法#xff09;#xff0c;是指在对问题求解时#xff0c;总是做出在当前看来是最好的选择。也就是说#xff0c;不从整体最优上加以考虑 —— 所做…算法进阶视频地址https://www.bilibili.com/video/BV1uA411N7c5
1. 贪心算法
贪心算法又称贪婪算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说不从整体最优上加以考虑 —— 所做出的是在某种意义上的局部最优解。
贪心算法并不保证会得到最优解但是在某些问题上贪心算法的解就是最优解。要会判断一个问题能否用贪心算法来计算。
1.1 找零问题
假设商店老板需要找零n元钱钱币的面额有100元、50元、20元、5元、1元如何找零使得所需钱币的数量最少 只考虑元不考虑角和分 def chaneg(t, n):t: 钱的面额n: 需要找零的金额m [0 for _ in range(len(t))] # t对应的使用次数for i, money in enumerate(t):m[i] n // money # 对应面额的数量n n % money # 还剩下的钱else: # n表示剩下没找开的钱return m, nif __name__ __main__:t [100, 50, 20, 5, 1]print(chaneg(t, 376)) # ([3, 1, 1, 1, 1], 0)print(chaneg(t, 376.5)) # ([3.0, 1.0, 1.0, 1.0, 1.0], 0.5)1.2 背包问题
一个小偷在某个商店发现 nnn 个商品第 iii 个商品价值 viv_ivi 元重 wiw_iwi 千克。他希望拿走的价值尽量高但他的背包最多只能容纳 WWW 千克的东西。他应该拿走哪些商品
背包问题再往下细分还有两种问题
问题10-1背包对于一个商品小偷要么把它完整拿走要么留下。不能只拿走一部分或把一个商品拿走多次。商品为金条
问题2分数背包对于一个商品小偷可以拿走其中任意一部分。商品为金沙
举例
商品1金v160,w110v_1 60, w_1 10v160,w110商品2银v2100,w220v_2 100, w_2 20v2100,w220商品3铜v3120,w330v_3 120, w_3 30v3120,w330背包容量W50W50W50
对于 0-1背包 和 分数背包贪心算法是否都能得到最优解为什么
思路先算一下三种商品的 价值/重量先装最贵的。
对于0-1背包
商品1金v160,w110v_1 60, w_1 10v160,w110, 单价6商品2银v2100,w220v_2 100, w_2 20v2100,w220, 单价5商品3铜v3120,w330v_3 120, w_3 30v3120,w330, 单价4背包容量W50W50W50
所以先拿商品1再拿商品2此时拿不走商品3了此时总价值160并不是最优解。所以 0-1背包 不能用贪心算法来解决。
对于分数背包
先拿商品1再拿商品2最后拿部分的商品3。
def fractional_backpack(goods, vol):goods: 商品 (价格, 重量)vol: 背包容量# 确定返回值strategy [0 for _ in range(len(goods))] # 对应的是排好序的goods# 拿走商品的总价值total_value 0for i, (price, weight) in enumerate(goods):if vol weight:strategy[i] 1# 更新volvol - weighttotal_value priceelse:strategy[i] vol / weight# 更新volvol 0total_value strategy[i] * pricebreakprint(Item : Times)for key, value in dict(zip(goods, strategy)).items():print(f{key} : {value})print(fTotal Value: {total_value})return strategy, total_valueif __name__ __main__:goods [(60, 10), (120, 30), (100, 20)]# 先对good进行排序 - 按照商品单位重量价值进行降序排序goods.sort(keylambda x: x[0] / x[1], reverseTrue)fractional_backpack(goods, 50)Item : Times(60, 10) : 1(100, 20) : 1(120, 30) : 0.6666666666666666Total Value: 240.01.3 拼接最大数字问题
有 nnn 个非负整数将其按照字符串拼接的方式拼接为一个整数如何拼接可以使得得到的整数最大
例32,94,128,1286,6,71可以拼接出的最大整数为94716321286128。
思路字符串比大小的顺序来进行
小坑128和1286怎么比
解决思路
a 128
b 1286a b if (ab) (ba) else b a解题方法
from functools import cmp_to_keydef xy_cmp(x, y):if x y y x:return 1elif x y y x:return -1else:return 0def number_join(ls):# 先将整数变为字符串ls list(map(str, ls)) # [32, 94, 128, 1286, 6, 71]# 按照第一个字符串排序ls.sort(keycmp_to_key(xy_cmp))return .join(ls)if __name__ __main__:ls [32, 94, 128, 1286, 6, 71]print(number_join(ls)) # 947163212861281.4 活动选择问题
假设有 nnn 个活动这些活动要占用同一片场地而场地在某时刻只能供一个活动使用。每个活动都有一个开始时间 sis_isi 和结束时间 fif_ifi 题目中时间以整数表述表示活动在 [si,fi)[s_i, f_i)[si,fi) 区间占用场地。问安排哪些活动能够使该场地举办的活动数量最多 贪心结论最先结束的活动一定是最优解的一部分。
证明假设 aaa 是所有活动中最先结束的活动bbb 是最优解中最先结束的活动。如果 aba bab结论成立如果 a≠ba \neq bab则 bbb 的结束时间一定晚于 aaa 的结束时间则此时用 aaa 替换掉最优解中的 bbbaaa 一定不与最优解中的其他活动时间重叠因此替换后的解也是最优解。
def activity_selection(activities):res []res.append(activities[0]) # 第一个活动是最先结束的活动for i in range(1, len(activities)):# 如果下一个活动的开始时间≥上一个活动的结束时间 - 不冲突if activities[i][0] res[-1][1]: # [0]: 开始时间; [1]: 结束时间res.append(activities[i])return resif __name__ __main__:activities [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9),(6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]# 保证活动是按照结束时间排好序的activities.sort(keylambda x: x[1])print(activity_selection(activities)) # [(1, 4), (5, 7), (8, 11), (12, 16)]2. 动态规划 (Dynamic Programming)
[概况]动态规划Dynamic Programming, DP是运筹学的一个分支是求解决策过程最优化的过程。20世纪50年代初美国数学家贝尔曼R.Bellman等人在研究多阶段决策过程的优化问题时提出了著名的最优化原理从而创立了动态规划。动态规划的应用极其广泛包括工程技术、经济、工业生产、军事以及自动化控制等领域并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
[原理]动态规划问世以来在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题用动态规划方法比用其它方法求解更为方便。
虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题但是一些与时间无关的静态规划(如线性规划、非线性规划)只要人为地引进时间因素把它视为多阶段决策过程也可以用动态规划方法方便地求解。
[概念引入]在现实生活中有一类活动的过程由于它的特殊性可将过程分成若干个互相联系的阶段在它的每一阶段都需要作出决策从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定它依赖于当前面临的状态又影响以后的发展。当各个阶段决策确定后就组成一个决策序列因而也就确定了整个过程的一条活动路线这种把一个问题看作是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程这种问题称为多阶段决策问题。在多阶段决策问题中各个阶段采取的决策一般来说是与时间有关的决策依赖于当前状态又随即引起状态的转移一个决策序列就是在变化的状态中产生出来的故有“动态”的含义称这种解决多阶段决策最优化的过程为动态规划方法。
[基本思想]动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中可能会有许多可行解。每一个解都对应于一个值我们希望找到具有最优值的解。动态规划算法与分治法类似其基本思想也是将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。与分治法不同的是适合于用动态规划求解的问题经分解得到子问题往往不是互相独立的。若用分治法来解这类问题则分解得到的子问题数目太多有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案而在需要时再找出已求得的答案这样就可以避免大量的重复计算节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到只要它被计算过就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样但它们具有相同的填表格式。 动态规划不是一种特定的算法而是一种算法思想。 2.1 从斐波那契数列看动态规划
斐波那契数列F11,F22F_1 1, F_2 2F11,F22, FnFn−1Fn−2F_n F_{n-1} F_{n -2}FnFn−1Fn−2练习使用递归和非递归的方法来求解斐波那契数列的第 nnn 项。
from cal_time import cal_fn_timedef fibnacci(n):if n 1 or n 2:return 1else:return fibnacci(n - 1) fibnacci(n - 2)cal_fn_time
def fibnacci_time(*args, **kwargs):return fibnacci(*args, **kwargs)cal_fn_time
def fibnacci_no_recurision(n):f [0, 1, 1]if n 2:for i in range(n - 2):num f[-1] f[-2]f.append(num)return f[n]if __name__ __main__:print(fibnacci_time(5)) # 5 0.0000 msprint(fibnacci_time(10)) # 55 0.0000 msprint(fibnacci_time(20)) # 6765 3.0372 msprint(fibnacci_time(30)) # 832040 243.0727 msprint(----------)print(fibnacci_no_recurision(5)) # 5 0.0000 msprint(fibnacci_no_recurision(10)) # 55 0.0000 msprint(fibnacci_no_recurision(20)) # 6765 0.0000 msprint(fibnacci_no_recurision(30)) # 832040 0.0000 msprint(fibnacci_no_recurision(50)) # 12586269025 0.0000 ms可以看到使用递归的fibnacci数列求解非常慢。这是因为递归有子问题的重复计算比如说求 F(5)F(5)F(5) 时会用到 F(4)F(4)F(4) 和 F(3)F(3)F(3)而求 F(4)F(4)F(4) 的时候会用到 F(3)F(3)F(3) 和 F(2)F(2)F(2)那么 F(3)F(3)F(3) 就被重复计算了算了两次。
而使用非递归的算法时因此计算结果都存在list中因此不会出现子问题重复计算的问题。而这种非递归的思想就是动态规划的思想。
动态规划的两个重点
最优子结构要想解决这个问题解决它的子问题就好递归式如Fabnacci重复子问题把重复计算的结构存起来
2.2 钢条切割问题
某公司出售钢条出售价格与钢条长度之间的关系如下表 问题现在有一段长度为 nnn 的钢条和上面的价格表求切割钢条方案使得总收益最大。
长度为4的钢条的所有切割方案如下(c方案为最优) 思考长度为 nnn 的钢条的不同切割方案有几种
答2n−12^{n-1}2n−1种方案。 一根钢条有 n−1n-1n−1 个切割点每个切割点都有切和不切两种方案所以是 2n−12^{n-1}2n−1种切割方案。 r[i]是最优的收益。 当我们求出前面的后面的最优解就可以直接用前面的来得出了。
2.2.1 递推式
设长度为 nnn 的钢条切割后最优收益值为 rnr_nrn可以得出递推式
rnmax(pn,r1rn−1,r2rn−2,...,rn−1r1)r_n \max(p_n, r_1 r_{n - 1}, r_2 r_{n - 2}, ..., r_{n - 1} r_1) rnmax(pn,r1rn−1,r2rn−2,...,rn−1r1)
第一个参数 pnp_npn 表示不切割其他 n−1n-1n−1 个参数分别表示另外 n−1n - 1n−1种不同切割方案对于方案 i1,2,...,n−1i1, 2, ..., n - 1i1,2,...,n−1 将钢条切割为长度为 iii 和 n−in - in−i 两段方案 iii 的收益为切割两段的最优收益之和 考察所有的 iii选择其中收益最大的方案
代码如下
def cut_rod_recursion_1(p, n):p: 钢条的价格, 其索引就是该价格下的长度n: 钢条的长度$$r_n \max(p_n, r_1 r_{n - 1}, r_2 r_{n - 2}, ..., r_{n - 1} r_1)$$if n 0:return 0else:res p[n] # 不切割的收益for i in range(1, n): # 1, n-1res max(res, cut_rod_recursion_1(p, i) cut_rod_recursion_1(p, n - i))return res2.2.2 最优子结构
可以将求解规模为 nnn 的原问题划分为规模更小的子问题完成一次切割后可以将产生的两段钢条看成两个独立的钢条切割问题。
组合两个子问题的最优解并在所有可能的两段切割方案中选取组合收益最大的构成原问题的最优解。
钢条切割满足最优子结构问题的最优解由相关子问题的最优解组合而成这些子问题可以独立求解。 钢条切割问题还存在更简单的递归求解方法
从钢条的左边切割下长度为 iii 的一段只对右边剩下的一段继续进行切割左边的不再切割递推式简化为: rnmax1≤i≤n(pirn−1)r_n \underset{1\le i \le n}{\max}(p_i r_{n - 1})rn1≤i≤nmax(pirn−1)不做切割的方案就可以描述为左边一段长度为 nnn收益为 pnp_npn剩余一段长度为0收益为 r00r_0 0r00。
代码如下
def cut_rod_recursion_2(p, n):$r_n \\underset{1\le i \le n}{\max}(p_i r_{n - 1})$if n 0:return 0else:res 0for i in range(1, n 1):res max(res, p[i] cut_rod_recursion_2(p, n - i))return res完整代码如下
import timedef cal_fn_time(fn):def wrapper(*args, **kwargs):t1 time.time()res fn(*args, **kwargs)t2 time.time()print(f{fn.__name__}s running time is: {(t2 - t1) * 1000:.4f} ms)return resreturn wrapperdef cut_rod_recursion_1(p, n):p: 钢条的价格, 其索引就是该价格下的长度n: 钢条的长度$$r_n \max(p_n, r_1 r_{n - 1}, r_2 r_{n - 2}, ..., r_{n - 1} r_1)$$if n 0:return 0else:res p[n] # 不切割的收益for i in range(1, n): # 1, n-1res max(res, cut_rod_recursion_1(p, i) cut_rod_recursion_1(p, n - i))return rescal_fn_time
def cut_rod_recursion_1_time(*args, **kwargs):return cut_rod_recursion_1(*args, **kwargs)def cut_rod_recursion_2(p, n):$r_n \\underset{1\le i \le n}{\max}(p_i r_{n - 1})$if n 0:return 0else:res 0for i in range(1, n 1):res max(res, p[i] cut_rod_recursion_2(p, n - i))return rescal_fn_time
def cut_rod_recursion_2_time(*args, **kwargs):return cut_rod_recursion_2(*args, **kwargs)if __name__ __main__:p [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]p_exp [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]print(cut_rod_recursion_1(p, 9)) # 25print(cut_rod_recursion_2(p, 9)) # 25print(cut_rod_recursion_1_time(p_exp, 15)) # 42 1671.4497 msprint(cut_rod_recursion_2_time(p_exp, 15)) # 42 12.9933 ms2.2.3 自顶向下的递归实现
def _cut_rod(p, n):if n 0:return 0q 0for i in range(1, n 1):q max(q, p[i] _cut_rod(p, n - i))return q递归的时候n-1说明n一直在减小所以是从上往下的递归。 为何自顶向下的递归实现的效率会这么差
时间复杂度: O(2n)O(2^n)O(2n) 可以从图中可以看到还是存在大量的重复子问题计算这样就会导致算法的效率很差。
2.3.4 动态规划解法
递归算法由于重复求解相同子问题效率极低因此可以使用动态规划的思想来做
每个子问题只求解一次保存求解的结果之后需要此问题时只需查找保存的结果 需要自底向上的算 代码如下
def cir_rod_dynamic_programming(p, n):使用动态规划的思想来实现自底向上的算$r_n \max(p_i r_{n - 1})$# 开一个列表用来存放结果r [0] # 长度为0时收益为0for i in range(1, n 1): # [1, n1]res 0for j in range(1, i 1): # i就相当于是nres max(res, p[j] r[i - j])r.append(res)return r[n]时间复杂度O(n2)O(n^2)O(n2)
时间复杂度自顶向下O(2n)O(2^{n})O(2n)自底向上O(n2)O(n^2)O(n2)
可以看到使用了动态规划算法的时间复杂度大幅度降低
2.3.4 重构解
如何修改动态规划算法使其不仅输出最优解还输出最优切割方案
对每个子问题保存切割一次时左边切下的长度 s[i]s[i]s[i]是用来记录左边切割的长度 对于i4i4i4s[i]2s[i] 2s[i]2说明4224 2 24222的价值已经知道了对于i5i5i5s[i]2s[i] 2s[i]2说明5235 2 35232的价值已经知道了3的最优价值也知道了所以总价值5813对于i9i9i9s[i]3s[i] 3s[i]3说明9279 2 79272的价值已经知道了7的s[i]1s[i]1s[i]1所以7167 1 6716以此类推…
def cut_rod_dp(p, n):# 开一个列表用来存放结果r [0] # 长度为0时收益也为0for i in range(1, n 1):res 0for j in range(1, i 1): # i就相当于是nres max(res, p[j] r[i - j])r.append(res)return r[n]def cut_rod_extend(p, n): # 重构解r [0]s [0]for i in range(1, n 1): # 从底向上算res_r 0 # 记录最优价值res_s 0 # 记录最优左边长度for j in range(1, i 1):if p[j] r[i - j] res_r:res_r p[j] r[i - j]res_s jr.append(res_r)s.append(res_s)return r[n], sdef cut_rod_solution(p, n):r, s cut_rod_extend(p, n) # 最优值和s表得到了solution []while n 0:solution.append(s[n]) # 先把左边的加进去n - s[n]return solutionif __name__ __main__:p [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]p_exp [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 27, 28, 30, 33, 36, 39, 40]print(cut_rod_dp(p, 10))r, s cut_rod_extend(p, 10)print(s)print(fPrice: {cut_rod_extend(p, 10)}, solution: {cut_rod_solution(p, 10)})# Price: (30, [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 10]), solution: [10]print(fPrice: {cut_rod_extend(p, 9)}, solution: {cut_rod_solution(p, 9)}) # [1, 6]# Price: (25, [0, 1, 2, 3, 2, 2, 6, 1, 2, 3]), solution: [3, 6]print(fPrice: {cut_rod_extend(p, 8)}, solution: {cut_rod_solution(p, 8)}) # [1, 6]# Price: (22, [0, 1, 2, 3, 2, 2, 6, 1, 2]), solution: [2, 6]2.3 动态规划问题关键特征
什么问题可以使用动态规划方法
有最优值的问题可以考虑使用动态规划最优子结构 原问题的最优解中涉及多少个子问题在确定最优解使用哪些子问题时需要考虑多少种选择 重叠子问题为避免重复计算动态规划是一种很好的方法 递推式在解决实际问题时是很难找的 2.4 最长公共子序列
一个序列的子序列是在该序列中删去若干元素后得到的序列。例ABCD和BDF都是ABCDEFG的子序列。
最长公共子序列LCS问题给定两个序列X和Y求X和Y长度最大的公共子序列。例XABBCBDEYDBBCDBLCS(X, Y)BBCD 注意这里并不是说LCS必须是连着的 应用场景长公共子序列是一个十分实用的问题它可以描述两段文字之间的“相似度”即它们的雷同程度从而能够用来辨别抄袭。对一段文字进行修改之后计算改动前后文字的最长公共子序列将除此子序列外的部分提取出来这种方法判断修改的部分往往十分准确。简而言之百度知道、百度百科都用得上。 字符串相似度比对 一个字符串的子串有2n2^n2n个包含空序列空序列是任意一个序列的子序列。 这道题是求最长的公共子序列因此是一个求最优的问题我们就要思考是否可以用动态规划的思想来做因此需要思考。
思考
暴力穷举法的时间复杂度是多少最长公共子序列是否具有最优子结构性质
2.4.1 定理
定理LCS的最优子结构令 Xx1,x2,...,xmXx_1, x_2, ..., x_mXx1,x2,...,xm 和 Yy1,y2,...,ynYy_1, y_2, ..., y_nYy1,y2,...,yn 为两个序列Zz1,z2,...,zkZz_1, z_2, ..., z_kZz1,z2,...,zk 为 XXX 和 YYY 的任意LCS。
如果 xmynx_m y_nxmyn则 zkxmynz_k x_m y_nzkxmyn 且 Zk−1Z_{k-1}Zk−1 是 Xm−1X_{m - 1}Xm−1 和 Yn−1Y_{n-1}Yn−1 的一个LCS。如果 xm≠ynx_m \ne y_nxmyn那么 zk≠xmz_k \ne x_mzkxm 且 意味着 ZZZ 是 Xm−1X_{m - 1}Xm−1 和 YYY 的一个LCS。如果 xm≠ynx_m \ne y_nxmyn那么 zk≠ynz_k \ne y_nzkyn 且 意味着 ZZZ 是 XXX 和 Yn−1Y_{n - 1}Yn−1 的一个LCS。
对于1假设 X A, B, C, D, YA, B, D它们的LCS是 ABD那么就可以说 A, B, C 和 A, B 的LCS是 A, B。意思就是说如果两个字符的最后一个字符相等那么两者同时扔掉这个相同的字符LCS也需要扔掉这个字符。
也可以用长度来理解X的长度是mmmY的长度是nnn它们的LCS长度是kkk。如果它们最后一个字符相等的话去掉这个相等的字符X的长度变为m−1m-1m−1Y的长度变为n−1n-1n−1LCS的长度变为k−1k-1k−1。
对于2和3假设 X A, B, C, D, YA, B, C这两个字符长的最后一个字符不相等那么LCS的长度等于X A, B, C和YA, B, C的LCS的长度 或者 等于X A, B, C, D和YA, B的LCS的长度这两个取最大值。
例子要求aABCBDAB与bBDCABA的LCS。
因为两个字符串的最后一个字符不同B ≠ A因此LCS(a, b)应该来源于LCS(a[: -1], b)与LCS(a, b[: -1])中更大的那一个。 因为两个字符串最后一位不相同因此对于两个字符串而言二者中的最后一位要想是LCS的一部分就必须不能同时是两个字符串的最后一位。这意味着对于字符串X而言LCS要想保留X[-1]那么Y就必须不能保留Y[-1]对于Y也是同理。 2.4.2 最优解推导式
最优解的推导式如下 灰色的表示LCS的具体字符串内容 c[i,j]{0若i0或j0c[i−1,j−1]1若i,j0且xiyimax(c[i,j−1],c[i−1,j])若i,j0且xi≠yic[i, j] \begin{cases} 0 若 i 0 或 j 0 \\ c[i - 1, j - 1] 1 若i,j 0且x_i y_i \\ \max(c[i, j-1], c[i-1,j]) 若i,j 0 且 x_i \ne y_i \end{cases} c[i,j]⎩⎨⎧0c[i−1,j−1]1max(c[i,j−1],c[i−1,j])若i0或j0若i,j0且xiyi若i,j0且xiyi
其中c[i,j]c[i, j]c[i,j] 表示 XiX_iXi 和 YjY_jYj 的LCS长度。
最终我们求的是 c[7,6]c[7, 6]c[7,6]就是LCS的长度。 第一行都是空串所以都是0 第二行如果两个字符串的最后一个字符相等那么都-1的LCS1即左上方的数值1 第三行因为两个字符串的最后一个字符不相等因此两个字符串分别-1再取二者的最大值即取Max(上方, 左方) 举个例子CA和CBA ≠ B因此LCS来自于 max([CA,C]LCS,[CB,C]LCS)\max([CA, C]_{\rm LCS}, [CB, C]_{\rm LCS})max([CA,C]LCS,[CB,C]LCS)。 再举个例子CA和ABA 不等于 B因此LCS来自于 max([CA,A]LCS,[AB,C]LCS)\max([CA, A]_{\rm LCS}, [AB, C]_{\rm LCS})max([CA,A]LCS,[AB,C]LCS)。 创建那个表的时候i0和j0都是默认的我们一行一行的填。对于 i1, j1而言左右和左上都有数因此是可以填的一行一行的我们就都可以填完了
2.4.3 LCS长度的代码实现
代码实现
def lcs_length(x, y):x: 字符串Xy: 字符串Ym len(x) # x的字符串长度n len(y) # y的字符串长度# 因为i0和j0并不在两个字符串长度范围内因此需要再扩充一行一列c [[0 for _ in range(n 1)] for _ in range(m 1)] # m1行, n1列[0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0]# 一行一行的填充值因为我们扩充了一行一列而一行一列我们不考虑因此是[1, m]和[1, n]for i in range(1, m 1): # [1, m]for j in range(1, n 1): # [1, n]# 因为i和j都是大于0的所以我们不考虑而且前面定义的c的时候也都赋0了虽然公式是x[i] y[j]但是我们的i和j都是从1开始的对应字符串应该是从0开始所以需要-1意思就是字符串x和y的索引应该-1而c的索引是不需要-1的i-1和j-1对于x和y而言不会越界因为i和j最小值为1,同理对c也不会越界if x[i - 1] y[j - 1]: # i和j位置上的字符相等看左上方的1c[i][j] c[i - 1][j - 1] 1else:c[i][j] max(c[i - 1][j], c[i][j - 1])# 打印一下填充后的二维列表for _ in c:print(_)return c[m][n]if __name__ __main__:x ABCBDABy BDCABAprint(lcs_length(x, y))[0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 1, 1, 1][0, 1, 1, 1, 1, 2, 2][0, 1, 1, 2, 2, 2, 2][0, 1, 1, 2, 2, 3, 3][0, 1, 2, 2, 2, 3, 3][0, 1, 2, 2, 3, 3, 4][0, 1, 2, 2, 3, 4, 4]42.4.4 LCS具体内容
现在我们只是知道LCS的长度但我们还没有确定LCS的具体内容。 我们看这个表可以看到灰色的表示LCS的具体字符串内容。我们观察发现当有斜着过来的表示该行和该列的字母是相等的匹配的那我们找的就是匹配的过程并确定它匹配的位置这样我们就可以确定LCS的具体内容。
2.4.5 TraceBack回溯法
思路TraceBack回溯从最后一个往回找。
最后[7, 6]是4它的箭头是↑表示它来自于上方即[6, 6][6, 6]的箭头是↖表示来自左上方来自左上方表示匹配 - A即[5, 5][5, 5]的箭头是 ↑表示来自上方即[4, 5][4, 5]的箭头是↖表示来自左上方来自左上方表示匹配 - B即[3, 4][3, 4]的箭头是←表示来自左方即[3, 3][3, 3]的箭头是↖表示来自左上方来自左上方表示匹配 - C即[2, 2][2, 2]的箭头是←表示来自左方即[2, 1][2, 1]的箭头是↖表示来自左上方来自左上方表示匹配 - B即[1, 0][1, 0]是空串停止回溯。因此可以确定最终的LCSBCBA TraceBack方法要求我们记录箭头 2.4.6 TraceBack回溯法代码实现
代码实现
def lcs_length(x, y):x: 字符串Xy: 字符串Ym len(x) # x的字符串长度n len(y) # y的字符串长度# 因为i0和j0并不在两个字符串长度范围内因此需要再扩充一行一列c [[0 for _ in range(n 1)] for _ in range(m 1)] # m1行, n1列[0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0]# 一行一行的填充值因为我们扩充了一行一列而一行一列我们不考虑因此是[1, m]和[1, n]for i in range(1, m 1): # [1, m]for j in range(1, n 1): # [1, n]# 因为i和j都是大于0的所以我们不考虑而且前面定义的c的时候也都赋0了虽然公式是x[i] y[j]但是我们的i和j都是从1开始的对应字符串应该是从0开始所以需要-1意思就是字符串x和y的索引应该-1而c的索引是不需要-1的i-1和j-1对于x和y而言不会越界因为i和j最小值为1,同理对c也不会越界if x[i - 1] y[j - 1]: # i和j位置上的字符相等看左上方的1c[i][j] c[i - 1][j - 1] 1else:c[i][j] max(c[i - 1][j], c[i][j - 1])# 打印一下填充后的二维列表for _ in c:print(_)return c[m][n]def lcs_record_arrows(x, y):m len(x)n len(y)c [[0 for _ in range(n 1)] for _ in range(m 1)]# 定义相同的二维数组用来记录箭头# 0: 没有方向(空串); 1: 左上方(↖); 2: 上方(↑); 3: 左方(←)arrow_ls [[0 for _ in range(n 1)] for _ in range(m 1)][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 0, 0, 0]for i in range(1, m 1):for j in range(1, n 1):if x[i - 1] y[j - 1]: # i和j位置上的字符相等看左上方的1c[i][j] c[i - 1][j - 1] 1arrow_ls[i][j] 1 # 确定↖elif c[i - 1][j] c[i][j - 1]: # 上方↑ (优先上方)c[i][j] c[i - 1][j]arrow_ls[i][j] 2else: # 左方←c[i][j] c[i][j - 1]arrow_ls[i][j] 3return c[m][n], arrow_lsdef lcs_traceback(x, y):回溯算法lcs_len, arrows lcs_record_arrows(x, y)# 确定最后一个位置i len(x)j len(y)# 存放LCS的具体字符res []# 当i 0或 j 0时停止while i 0 and j 0: # 否命题是或则逆命题是与if arrows[i][j] 1: # 来自↖匹配的res.append(x[i - 1]) # 和之前一样对于x和y而言还是要-1的# 确定下一步怎么走i - 1j - 1elif arrows[i][j] 2: # 来自↑不匹配的i - 1elif arrows[i][j] 3: # 来自←不匹配的j - 1# 因为我们是回溯所以res是倒着的res.reverse() # list.reverse()没有返回值# .join(map(str, res))是常见的把list转换为strreturn .join(map(str, res))if __name__ __main__:x ABCBDABy BDCABAprint(lcs_length(x, y))print()[0, 0, 0, 0, 0, 0, 0][0, 0, 0, 0, 1, 1, 1][0, 1, 1, 1, 1, 2, 2][0, 1, 1, 2, 2, 2, 2][0, 1, 1, 2, 2, 3, 3][0, 1, 2, 2, 2, 3, 3][0, 1, 2, 2, 3, 3, 4][0, 1, 2, 2, 3, 4, 4]4lcs_length, arrow_ls lcs_record_arrows(x, y)print(lcs_length) # 4for _ in arrow_ls:print(_)print()[0, 0, 0, 0, 0, 0, 0][0, 2, 2, 2, 1, 3, 1][0, 1, 3, 3, 2, 1, 3][0, 2, 2, 1, 3, 2, 2][0, 1, 2, 2, 2, 1, 3][0, 2, 1, 2, 2, 2, 2][0, 2, 2, 2, 1, 2, 1][0, 1, 2, 2, 2, 1, 2]res lcs_traceback(x, y)print(res) # B C B A3. 欧几里得算法
3.1 最大公约数
约数如果整数 aaa 能被整数 bbb 整除那么 aaa 叫做 bbb 的倍数bbb 叫做 aaa 的约数。
给定两个整数 a,ba, ba,b两个数的所有公共约数中的最大值即为最大公约数 (Greatest Common Divisor, GCD)。
例子12与16的最大公约数是4. 如何计算两个数的最大公约数
欧几里得辗转相除法欧几里得算法《九章算术》更相减损术 这两个算法的本质是一样的前者是除后者是减 3.2 欧几里得算法
欧几里得算法的公式如下
gcd(a,b)gcd(b,amodb)\gcd(a, b) \gcd(b, a \ {\rm mod} \ b) gcd(a,b)gcd(b,a mod b) mod % —— 取余数 例子gcd(60, 21) gcd(21, 18) gcd(18, 3) gcd(3, 0) 3
代码实现
def gcd(a, b):最后的b肯定会变为零此时a就是最大公约数if b 0:return aelse:return gcd(b, a % b)def gcd_no_recursion(a, b):while b 0:tmp a % ba bb tmpreturn aif __name__ __main__:print(gcd(12, 16)) # 4print(gcd_no_recursion(12, 16)) # 43.3 应用实现分数计算
利用欧几里得算法实现一个分数类支持分数的四则运算。
class Fraction:def __init__(self, a, b):a: 分子b: 分母self.a aself.b b# 默认约分divisor self.gcd(self.a, self.b)self.a / divisorself.b / divisorstaticmethoddef gcd(a, b):while b 0:tmp a % ba bb tmpreturn astaticmethoddef lcm(a, b): # 最小公倍数(least common multiple)formula:divisor gcd(a, b)(a / divisor) * (b / divisor) * divisor a * b / divisordivisor Fraction.gcd(a, b)return a * b / divisordef __add__(self, other):# 两个分子加法先通分a self.ab self.bc other.ad other.bdenominator self.lcm(b, d) # 分母# 让分子增加相同的倍数numerator a * (denominator / b) c * (denominator / d)return Fraction(numerator, denominator)def __sub__(self, other):# 两个分子加法先通分a self.ab self.bc other.ad other.bdenominator self.lcm(b, d) # 分母# 让分子增加相同的倍数numerator a * (denominator / b) - c * (denominator / d)return Fraction(numerator, denominator)def __mul__(self, other):a self.ab self.bc other.ad other.breturn Fraction(a * c, b * d)def __truediv__(self, other):a self.ab self.bc other.ad other.breturn Fraction(a * d, b * c)def __str__(self):return %d/%d % (self.a, self.b)if __name__ __main__:f Fraction(30, 15)print(f)a Fraction(1, 3)b Fraction(1, 2)print(a b) # 5/6print(b - a) # 1/6print(a * b) # 1/6print(a / b) # 2/34. RSA加密算法
4.1 密码与加密 我们常用的password是口令和密码不一样 传统密码加密算法是秘密的 凯撒密码每个密码往后移动3位这种密码相对不安全可以通过暴力枚举破解 现代密码系统加密算法是公开的秘钥是秘密的
秘钥一般指密钥。 密钥是一种参数它是在明文转换为密文或将密文转换为明文的算法中输入的参数。密钥分为
对称加密一个秘钥可以用来加密也可以用来解密非对称加密需要两个秘钥一个用来加密一个用来解密
4.2 RSA加密算法
RSA非对称加密系统
公钥用来加密是公开的私钥用来解密是私有的 M是明文 加密用的是公钥 C是密文 解密用的是私钥 4.3 RSA加密算法过程
随机选取两个质数ppp和qqq计算npqn pqnpq选取一个与Φ(n)\Phi(n)Φ(n)互质的小奇数eee, Φ(n)(p−1)(q−1)\Phi(n) (p - 1)(q - 1)Φ(n)(p−1)(q−1)对模Φ(n)\Phi(n)Φ(n)计算eee的乘法逆元ddd即满足(e∗d)modΦ(n)1(e*d) \mod \Phi(n) 1(e∗d)modΦ(n)1公钥(e,n)(e, n)(e,n)私钥(d,n)(d, n)(d,n)
加密过程cmemodnc m^e \mod ncmemodn - c m ** e % n解密过程mcdmodnm c^d \mod nmcdmodn - m c ** d % n Q为什么RAS算法难破解 A两个质数算乘法很容易但是把一个大整数拆成两个质数很难。
15 - 3 * 5 但对于一个大的整数而言拆成两个质数的乘积就很难求解。
我们知道公钥eee和nnn现在想求私钥的ddd。那么我们需要知道Φ(n)\Phi(n)Φ(n)要想知道Φ(n)\Phi(n)Φ(n)我们就要知道ppp和qqq而ppp和qqq是两个质数二者的乘积等于nnn求这两个质数的过程很难。
