python实现最长公共子序列

yipeiwu_com5年前Python基础

最长公共子序列python实现,最长公共子序列是动态规划基本题目,下面按照动态规划基本步骤解出来。

1.找出最优解的性质,并刻划其结构特征

序列a共有m个元素,序列b共有n个元素,如果a[m-1]==b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是a[:m-1]和b[:n-1]的最长公共子序列长度+1;如果a[m-1]!=b[n-1],那么a[:m]和b[:n]的最长公共子序列长度就是MAX(a[:m-1]和b[:n]的最长公共子序列长度,a[:m]和b[:n-1]的最长公共子序列长度)。

2.递归定义最优值


3.以自底向上大方式计算出最优值

python代码如下:

def lcs(a,b): 
  lena=len(a) 
  lenb=len(b) 
  c=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  flag=[[0 for i in range(lenb+1)] for j in range(lena+1)] 
  for i in range(lena): 
    for j in range(lenb): 
      if a[i]==b[j]: 
        c[i+1][j+1]=c[i][j]+1 
        flag[i+1][j+1]='ok' 
      elif c[i+1][j]>c[i][j+1]: 
        c[i+1][j+1]=c[i+1][j] 
        flag[i+1][j+1]='left' 
      else: 
        c[i+1][j+1]=c[i][j+1] 
        flag[i+1][j+1]='up' 
  return c,flag 
 
def printLcs(flag,a,i,j): 
  if i==0 or j==0: 
    return 
  if flag[i][j]=='ok': 
    printLcs(flag,a,i-1,j-1) 
    print(a[i-1],end='') 
  elif flag[i][j]=='left': 
    printLcs(flag,a,i,j-1) 
  else: 
    printLcs(flag,a,i-1,j) 
     
a='ABCBDAB' 
b='BDCABA' 
c,flag=lcs(a,b) 
for i in c: 
  print(i) 
print('') 
for j in flag: 
  print(j) 
print('') 
printLcs(flag,a,len(a),len(b)) 
print('') 

运行结果输出如下:


4.根据计算最优值得到的信息,构造最优解

上图是运行结果,第一个矩阵是计算公共子序列长度的,可以看到最长是4;第二个矩阵是构造这个最优解用的;最后输出一个最优解BCBA。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

vscode 配置 python3开发环境的方法

vscode 配置 python3开发环境的方法

vscode来写python,配置灵活,界面美观,是个非常好的选择。我这里是在ubuntu系统下配置vscode的python3开发环境,当然也可以参照本文在其它操作系统下配置vscod...

Python进行数据科学工作的简单入门教程

Python进行数据科学工作的简单入门教程

Python拥有着极其丰富且稳定的数据科学工具环境。遗憾的是,对不了解的人来说这个环境犹如丛林一般(cue snake joke)。在这篇文章中,我会一步一步指导你怎么进入这个PyDat...

python 合并文件的具体实例

支持两种用法:(1)合并某一文件夹下的所有文件(忽略文件夹等非文件条目)(2)显示的合并多文件。复制代码 代码如下:import sysimport os'''  &...

解决Atom安装Hydrogen无法运行python3的问题

解决Atom安装Hydrogen无法运行python3的问题

Atom是一款功能强大的跨平台编辑器,插件化的解决方案为atom社区的繁荣奠定了基础。任何人都可以把自己做的组件贡献在github上,并能方便的安装到Atom上使用。 Jupyter N...

python文件名和文件路径操作实例

Readme: 在日常工作中,我们常常涉及到有关文件名和文件路径的操作,在python里的os标准模块为我们提供了文件操作的各类函数,本文将分别介绍“获得当前路径”“获得当前路径下的所有...