【算法进阶2-动态规划】最长公共子序列、欧几里得算法-分数、RSA算法-暗码于加密
1 最长公共子序列2 欧几里得算法
2.1 欧几里得算法-分数
3 RSA算法-暗码于加密
1 最长公共子序列
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMWFkYTM1MjhlYjBhNGQ3ZWFkY2M0MWYwOTVmODRhZjQucG5n
-个序列的子序列是在该序列中删去若干元素后得 到的序列。
例:“ABCD”和“BDF”都是“ABCDEFG”的子序列
最长公共子序列(LCS)问题:给定两个序列X和Y，求X和Y长度最大的公共子序列。
例:X="ABBCBDE" Y="DBBCDB" LCS(X,Y)="BBCD"
应用场景:字符串相似度比对
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvMTdlMTE1ZTJjZTM4NGVjOWEzMjgwZGE3YWI1MDdiODgucG5n
from typing import Tuple
def lcs_length(x: str, y: str) -> int:
"""
计算两个字符串的最长公共子序列 (LCS) 的长度。
使用动态规划方法解决LCS问题。LCS问题是指在两个字符串中找到一个最长的子序列，
使得这个子序列在两个字符串中都出现，并且保持其相对顺序不变。
:param x: 第一个字符串
:param y: 第二个字符串
:return: 返回两个字符串的最长公共子序列的长度
"""
m = len(x)# 第一个字符串的长度
n = len(y)# 第二个字符串的长度
# 创建一个 (m+1) x (n+1) 的二维列表 c，用于存储子问题的解
# c 表示字符串 x 的前 i 个字符和字符串 y 的前 j 个字符的最长公共子序列的长度
c = [ for _ in range(m + 1)]
# 填充二维列表 c
for i in range(1, m + 1):# 遍历字符串 x 的每个字符
for j in range(1, n + 1):# 遍历字符串 y 的每个字符
if x == y:# 如果 x 的第 i 个字符等于 y 的第 j 个字符
# 如果字符匹配，当前最长公共子序列的长度是左上角的值 + 1
c = c + 1
else:
# 如果字符不匹配，取上方或左方的最大值
c = max(c, c)
# 打印二维列表 c 的值（用于调试）
for _ in c:
print('列表的值是：', _)
# 返回最长公共子序列的长度，即 c
return c
# print(lcs_length("ABCBDAB", "BDCABA"))# 4
# 列表的值是：
# 列表的值是：
# 列表的值是：
# 列表的值是：
# 列表的值是：
# 列表的值是：
# 列表的值是：
# 列表的值是：
def lcs(x: str, y: str) -> Tuple:
"""
计算两个字符串的最长公共子序列 (LCS) 的长度，并生成动态规划表。
使用动态规划方法求解两个字符串的最长公共子序列问题，并返回
长度以及记录方向的表，用于后续的LCS路径恢复。
:param x: 第一个字符串
:param y: 第二个字符串
:return: 返回一个元组，包含两个元素：
- LCS的长度
- 动态规划表 b，其中 b 表示到达位置 (i, j) 时的方向
"""
m = len(x)# 第一个字符串的长度
n = len(y)# 第二个字符串的长度
# 创建一个 (m+1) x (n+1) 的二维列表 c，用于存储子问题的解
# c 表示字符串 x 的前 i 个字符和字符串 y 的前 j 个字符的最长公共子序列的长度
c = [ for _ in range(m + 1)]
# 创建一个 (m+1) x (n+1) 的二维列表 b，用于记录方向
# b 表示到达位置 (i, j) 时的方向
# "←" 表示来自左上方（匹配），
# "↑" 表示来自上方（不匹配，向上移动），
# "↖" 表示来自左方（不匹配，向左移动）
b = [['*' for _ in range(n + 1)] for _ in range(m + 1)]
# 填充二维列表 c 和 b
for i in range(1, m + 1):
for j in range(1, n + 1):
if x == y:# 如果 x 的第 i 个字符等于 y 的第 j 个字符
# 如果字符匹配，当前最长公共子序列的长度是左上角的值 + 1
c = c + 1
b = "←"# 方向来自于左上方（匹配）
elif c > c:# 如果来自上方的值大于来自左方的值
# 如果上方的值更大，选择上方的值
c = c
b = "↑"# 方向来自于上方（不匹配，向上移动）
else:
# 如果左方的值更大或相等，选择左方的值
c = c
b = "↖"# 方向来自于左方（不匹配，向左移动）
# 返回最长公共子序列的长度和方向记录表
return c, b
c, b = lcs("ABCBDAB", "BDCABA")
for _ in b:
print(_)
# ['*', '*', '*', '*', '*', '*', '*']
# ['*', '↖', '↖', '↖', '←', '↖', '←']
# ['*', '←', '↖', '↖', '↖', '←', '↖']
# ['*', '↑', '↖', '←', '↖', '↖', '↖']
# ['*', '←', '↖', '↑', '↖', '←', '↖']
# ['*', '↑', '←', '↖', '↖', '↑', '↖']
# ['*', '↑', '↑', '↖', '←', '↖', '←']
# ['*', '←', '↑', '↖', '↑', '←', '↖']
def lcs_traceback(x: str, y: str) -> str:
"""
根据动态规划表回溯，找出两个字符串的最长公共子序列 (LCS)。
使用动态规划表 `b` 来回溯最长公共子序列的路径，并从结果表 `c` 中
获取最长公共子序列的字符。最终返回最长公共子序列的字符串。
:param x: 第一个字符串
:param y: 第二个字符串
:return: 返回两个字符串的最长公共子序列（LCS）的字符串表示
"""
# 调用 lcs 函数获取动态规划表 c 和方向记录表 b
c, b = lcs(x, y)
i = len(x)# 初始化 i 为第一个字符串的长度
j = len(y)# 初始化 j 为第二个字符串的长度
res = []# 用于存储回溯得到的 LCS 字符
# 根据方向记录表 b 从表的右下角开始回溯到左上角
while i > 0 and j > 0:
if b == "←":
# 如果方向来自于左上方（匹配），则当前字符是 LCS 的一部分
res.append(x)
i -= 1# 移动到前一个字符
j -= 1# 移动到前一个字符
elif b == "↑":
# 如果方向来自于上方，则移动到上方的子问题
i -= 1
else:# '↖'
# 如果方向来自于左方，则移动到左方的子问题
j -= 1
# 由于回溯过程中字符是从 LCS 的末尾开始添加的，所以需要反转结果列表
return "".join(res[::-1])
print(lcs_traceback("ABCBDAB", "BDCABA"))# BDAB
2 欧几里得算法
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjEyMWFlYWE4NGRjNDZmMDk3ZDY3NGIxZjRlMjU4ZTQucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvOWNjODllNzE2NDM5NGI1YWFiMDFlMmY1MzcwMWJkNDcucG5n
def gcd(a: int, b: int) -> int:
"""
递归求解两个数的最大公约数 (GCD)。
使用欧几里得算法通过递归的方式计算两个整数的最大公约数。
当第二个数 b 为 0 时，最大公约数是第一个数 a。
:param a: 第一个整数
:param b: 第二个整数
:return: 返回 a 和 b 的最大公约数
"""
if b == 0:
return a# 基本情况：当 b 为 0 时，a 是最大公约数
else:
# 递归调用：计算 b 和 a % b 的最大公约数
return gcd(b, a % b)
print(gcd(12, 16))# 4
def gcd2(a: int, b: int) -> int:
"""
非递归求解两个数的最大公约数 (GCD)。
使用欧几里得算法通过迭代的方式计算两个整数的最大公约数。
通过不断更新 a 和 b 直到 b 为 0，此时 a 就是最大公约数。
:param a: 第一个整数
:param b: 第二个整数
:return: 返回 a 和 b 的最大公约数
"""
while b > 0:
r = a % b# 计算 a 除以 b 的余数
a = b# 更新 a 为 b
b = r# 更新 b 为余数
return a# 当 b 为 0 时，a 是最大公约数
print(gcd2(12, 16))# 4
2.1 动态规划之欧几里得算法-分数
class Fraction:
def __init__(self, a: int, b: int):
"""
初始化一个分数对象，并将其化简为最简分数。
:param a: 分子
:param b: 分母
"""
self.a = a
self.b = b
# 计算最大公约数
x = self.gcd(a, b)
# 将分子和分母除以最大公约数，化简为最简分数
self.a /= x
self.b /= x
@staticmethod
def gcd(a: int, b: int) -> int:
"""
非递归求解两个数的最大公约数 (GCD)。
使用欧几里得算法通过迭代的方式计算两个整数的最大公约数。
通过不断更新 a 和 b 直到 b 为 0，此时 a 就是最大公约数。
:param a: 第一个整数
:param b: 第二个整数
:return: 返回 a 和 b 的最大公约数
"""
while b > 0:
r = a % b# 计算 a 除以 b 的余数
a = b# 更新 a 为 b
b = r# 更新 b 为余数
return a# 当 b 为 0 时，a 是最大公约数
def __str__(self) -> str:
"""
返回分数的字符串表示形式。
:return: 返回分数的字符串表示，例如 "3/4"
"""
return f"{int(self.a)}/{int(self.b)}"
@staticmethod
def zgs(a: int, b: int) -> int:
"""
计算两个数的最小公倍数 (Least Common Multiple, LCM)。
使用公式 LCM(a, b) = abs(a * b) / GCD(a, b) 来计算最小公倍数。
:param a: 第一个整数
:param b: 第二个整数
:return: 返回 a 和 b 的最小公倍数，类型为整数
"""
x = Fraction.gcd(a, b)# 调用静态方法 gcd 计算最大公约数
return a * b // x# 根据公式计算最小公倍数，使用整数除法返回整数结果
def __add__(self, other: 'Fraction') -> 'Fraction':
# 3/5 + 2/7
"""
重载加法运算符，实现两个分数相加。
通过计算两个分数的最小公倍数来统一分母，并计算新分数的分子。
:param self: 第一个分数对象
:param other: 第二个分数对象
:return: 返回两个分数相加后的结果，作为新的 Fraction 对象
"""
a = self.a# 当前分数的分子
b = self.b# 当前分数的分母
c = other.a# 另一个分数的分子
d = other.b# 另一个分数的分母
denominator = self.zgs(b, d)# 计算两个分数分母的最小公倍数
numerator = a * denominator // b + c * denominator // d# 计算新分数的分子，使用整数除法确保结果为整数
return Fraction(int(numerator), int(denominator))# 返回新的 Fraction 对象，表示两个分数相加的结果
# f = Fraction(30, 16)
# print(f)# 输出 15/8
a = Fraction(3, 4)
b = Fraction(1, 2)
print(a + b)# 5/6
3 RSA算法-暗码于加密
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjBjZjA3N2M2ZDcyNDdiMjk4Zjk1YzEzYjA0YTE1NmQucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvNjJhMjM1MDkxYjE3NDliMjk0MDdmYjJiM2ZjODA1ODcucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvN2EwYTk1YmQzYTRhNDc1NmI0NzU5OTFlNGNlMGEzZDMucG5n
https://dis.qidao123.com/imgproxy/aHR0cHM6Ly9pLWJsb2cuY3NkbmltZy5jbi9kaXJlY3QvYmU0NjI4MTliYjc1NDcwOWFiNTIzMmRhYTlmMmQwMDMucG5n
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金
页:
[1]