神剑山庄资源网 Design By www.hcban.com
最长公共子序列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,最长公共子序列
神剑山庄资源网 Design By www.hcban.com
神剑山庄资源网
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件!
如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
神剑山庄资源网 Design By www.hcban.com
暂无python实现最长公共子序列的评论...
更新日志
2024年10月02日
2024年10月02日
- 孙悦.1996-伙伴【正大国际】【WAV+CUE】
- 纪钧瀚《钢琴阅读时光 雨中书店聆听轻音乐》[FLAC/分轨][399.62MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[320K/MP3][87.4MB]
- 证声音乐图书馆《走向自然 疗心爵士乐》[FLAC/分轨][184.94MB]
- 陈慧娴.2018-Priscilla-Ism演唱会3CD(2024环球红馆40复刻系列)【环球】【WAV+CUE】
- 郑秀文.1999-我应该得到(国)【华纳】【WAV+CUE】
- 陈家慧.2011-钢琴酒吧2CD【龙吟唱片】【WAV+CUE】
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[320K/MP3][45.01MB]
- 证声音乐图书馆《雨季 蓝调吉他 Rainy Blues》[FLAC/分轨][109.13MB]
- 赞多《序章》[320K/MP3][45.54MB]
- 许巍.2004-每一刻都是崭新的【步升大风】【WAV+CUE】
- 群星.2024-四方馆影视原声带【韶愔音乐】【FLAC分轨】
- 陈雷.1997-安锁咧【金圆唱片】【WAV+CUE】
- 关淑怡.2013-MY.FAVORITE.SK.3CD【环球】【WAV+CUE】
- Sweety.2006-花言乔语【丰华】【WAV+CUE】