第六章 算法设计技术.ppt

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