第六章 算法设计技术.ppt

  1. 1、本文档共138页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第六章算法设计技术要点

nv = v; for(i = f; i 0; i--) { while (q[i-1][nv-1] + p[i][nv] q[i][nv]) nv--; way[i] = nv--; } return q[f][v]; } void main() { int i, f, v, p[F][V], way[F]; init(f, v, p); printf(最大好看程度为 %d\n, sove(p, f, v, way)); printf(插有鲜花的花瓶为:\n); for(i = 1; i = f; i++) printf( %4d, way[i]); printf(\n); } 【例6.10】 求两字符序列的最长公共字符子序列 一个字符子序列是指从给定字符序列中随意去掉几个字符(可能一个也不去掉),包留的字符不改变其前后相对顺序,所形成的字符列。 字符序列X = x0,x1,…,xm-1, 字符序列Y = y0,y1,…,yk-1” 是X的子序列,要求对X存在一个严格的递增下标序列i0,i1,…,ik-1使得对所有的j = 0,1,…,k-1,有Xij = yj。 例如,X = ABCBDAB,Y= BCDB是X的一个子序列。 给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。现在问题要求已知两序列A和B的最长公共子序列。 如采用列举A的所有子序列,并一一检查其是否又是B的子序列,并随时记录所发现的公共子序列,最终求出最长公共子序列。这种方法因耗时太多而不可取。 考虑最长公共子序列问题如何分解成子问题。设 A = a0,a1,…,am-1, B = b0,b1,…,bn-1, Z = z0,z1,…,zk-1” 为它们的最长公共子序列。不难证明有以下性质: 1) 如果am-1 = bn-1,则zk-1 = am-1 = bn-1,且z0,z1,…,zk-2是a0,a1,…,am-2和b0,b1,…,bn-2的一个最长公共子序列; 2) 如果am-1 != bn-1,则若zk-1 != am-1,蕴含z0,z1,…,zk-1是a0,a1,…,am-2和b0,b1,…,bn-1的一个最长公共子序列; 3) 如果am-1 != bn-1,则若zk-1 != bn-1,蕴含z0,z1,…,zk-1是a0,a1,…,am-1和b0,b1,…,bn-2的一个最长公共子序列。 这样,在找A和B的公共子序列时, 如有am-1 = bn-1,则进一步解决一个子问题,找 “a0,a1,…,am-2” 和 “b0,b1,…,bn-2”的一个最长公共子序列; 如果am-1!= bn-1,则要解决两个子问题, 找出 “a0,a1,…,am-2” 和 “b0,b1,…,bn-1”的一个最长公共子序列,和 找出 “a0,a1,…,am-1” 和 “b0,b1,…,bn-2”的一个最长公共子序列。再取两者中的较长者作为A和B的最长公共子序列。 定义c[i][j]为序列a0,a1,…,ai-1和b0,b1,…,bj-1的最长公共子序列长度,计算c[i][j]可递归地表述如下: c[i][j]=0, 如果i = 0,或 j = 0; c[i][j]=c[i-1][j-1]+1,如果i,j0,且a[i-1]==b[j-1] c[i][j]=max(c[i][j-1], c[i-1][j]), 如果 i, j 0,且 a[i-1] != b[j-1] 根据以上算式写出计算两个序列最长公共子序列的长度的函数如下: #define N 100 int c[N][N]; int lcs_len(char *a, char *b) { int m = strlen(a), n = strlen(b), i, j; for(i = 0; i = m; i++) c[i][0] = 0; for(j = 1; j = n; j++) c[0][j] = 0; for(i = 1; i = m; i++) for(j = 1; j = n; j++) if(a[i-1]==b[j-1]) c[i][j]=c[i-1][j-1]+1; else if (c[i-1][j] = c[i][j-1]) c[i][j] = c[i-1][j]; else c[i][j] = c[i][j-1]; return c[m][n]; } 因为c[i][j]的产生仅依赖于c[i-1

文档评论(0)

dajuhyy + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档