软件水平考试常用算法设计方法

　　考虑最长公共子序列问题如何分解成子问题，设A=“a0，a1，…，am-1”，B=“b0，b1，…，bm-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，…，bm-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-2”和“b0，b1，…，bj-1”的最长公共子序列的长度，计算c[i][j]可递归地表述如下：
　　（1）c[i][j]=0 如果i=0或j=0；
　　（2）c[i][j]= c[i-1][j-1]+1 如果I，j>0，且a[i-1]=b[j-1]；
　　（3）c[i][j]=max（c[i][j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
　　按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1]，故可以从c[m][n]开始，跟踪c[i][j]的产生过程，逆向构造出最长公共子序列。细节见程序。
　　# include
　　# include
　　# define N 100
　　char a[N],b[N],str[N];
　　
　　int lcs_len(char *a, char *b, int c[ ][ N])
　　{ int m=strlen(a), n=strlen(b), i,j;
　　 for (i=0;i<=m;i++) c[i][0]=0;
　　 for (i=0;i<=n;i++) c[0][i]=0;
　　 for (i=1;i<=m;i++)
　　 for (j=1;j<=m;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];
　　}
　　
　　char *buile_lcs(char s[ ],char *a, char *b)
　　{ int k, i=strlen(a), j=strlen(b);
　　 k=lcs_len(a,b,c);
　　 s[k]=’\0’;
　　 while (k>0)
　　 if (c[i][j]==c[i-1][j]) i--;
　　 else if (c[i][j]==c[i][j-1]) j--;
　　 else { s[--k]=a[i-1];
　　 i--; j--;
　　 }
　　 return s;
　　}
　　
　　void main()
　　{ printf (“Enter two string

上一页  [1] [2] [3]