资源描述：
《最长公共子序列论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、最长公共了序列论文13计科行知班隋砚丹20130201101、问题描述_个给定序列的子序列是在该序列屮删去若T元素后得到的序列。确切地说，若给定序列X二,则另一序列Z二是X的子序列是指存任f严格递增的下标序列〈il,i2,…，ik>,使得对于所冇戶，2,…,k有Xij二Zj例如，序列Z二是序列X二的子序列，相应的递增卜标序列为〈2,3,5,7>o给定两个序列X和Y,当另一序列Z既是X的子序列乂是Y的子序列吋，称Z是序列X和Y的公共子序列。例如,X=〈A,B,C,B,D,A,B>和Y二,则序列是X和Y的一个公!
2、WU也玄和Y的一个公共了序列。而且，后者是X和Y的•个最长公共子序列，因为X和Y没有大于4的公共子序列。给定两个序列X二和Y=,要求找出X和Y的一个最长公共子序列。［输入文件】输入文件共有两行，每行为个由大写字母构成的长度不超过200的字符串，表示序列X和Y。【输出文件】输出文件第一行为一个非负整数，表示所求得的。2、问题分析、推导过程动态规划可以有效地解决此问题。下血按照动态规划算法设计的各个步骤设计解决问题的有效算法。2.1、最长公共了序列的结构穷举搜索法是最容易想到的算法。对于X的所有子序列，检查它是否是Y的子序列，从而
3、确定它是否为X和Y的公共子序列。并且子啊搜索过程中记录最长的公共了序列。X的所冇了序列都检查过后即可求出X和Y的最长公共了序列。X的每个子序列相应的卜-标集{1,2,・・・，m}的一个子集。因此，共有2"个不同的子序列，从而穷举搜索法需要指数时间。事实上，最长公共了序列问题具冇最优了结构性质。设序列X={XbX2,・・•，X」和Y={YbY2,•••,YJ的最长公共子序列为Z={zi,Z2,•・•，Zm},则(1)、若Xa=Yn,则Zk=Xm=Y„.且ZkT是Xm-1和Yn-1的最长公共子序列;(2)、若右工£,且ZkHXm，则Z是Xnrl和Y的最长公共子序列;(3)、若X»HYn
4、,且ZkHYm,则Z是X和Yn-1的最长公共子序列。其中,Xm-1={XI,X2,・・・,Xm-1};和Yn_l={Y1,Y2,・・・，Yn-1}；Zk-1={Z1,Z2,・・・，Zk—l}。证明：(1)用反证法。若ZkHXm,则{Zl,Z2,・・・，Zk,Xm}是X和Y的长度为K+l的公共了序列。这与Z是X和Y的最长公共了序列矛盾。因此，必有Zk=Xm=Yno由此可知,Zk-l是XnLL和Yn-l的长度为K-1的公共子序列。Xm-1和Yn-1有公共长度大于k的公共子序列。此为矛盾。故Zk-1是Xm-1和Yn-1的最长公共子序列。(2)由于ZkHXm,Z是Xm-1和Y的最长公共子序
5、列。若Xm-1有长度大于k的公共了序列W,则W也是X和Y的长度人于k的最长公共了序列。这与Z是X与Y的最长公共了序列矛盾。由此即知，Z是Xm-l和Y的最长公共子序列。(3)与(2)的证明相似，同用反证法。由此叮见,两个序列的授长公共了序列包含了这两个序列的前缀的最长公共了序列。由此，最长公共子序列具有最有子结构性质。2.2、了问题的递归结构由最长公共子序列问题的最优子结构性质可知，要找出X二{x】，X2,・・•,xj和Y={yi,yy2,•••,yj的最长公共子序列,可按以下方式递归计算:当Xm=Yn时,找出Xm-1AjYn-1的最长公共子序列,然后在其尾部加上Xm(=Yn)即可得
6、到X和Y的最长公共了序列。当人工人时，必须解决两个问题，即找到Xni-l和Y的一个最长公共子序列及X和Yn-l的一个最长公共子序列。这两个公共子序列小较长者即为X和Y的最长公共子序列。由此递归结构容易看出最长公共了序列问题具有了问题的重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算X和Yn-l及Xm-1和Y的一个最长公共子序列。而这两个子问题都包含一个公共问题，即计算Xm-1和Yn-l的最长公共了序列。首先建立子问题的最优值的递归关系。用C[i][j]记录序列X和Y的最长公共子序列的长度。-其中Xi={Xl,X2,・・・，Xi)；Y={Y1,Y2,・・・，Yj}。当i=0
7、或j二0时，空序列是X和Y的最长公共子序列，故此时C[i][j]=Oo在其他情况卜,由最优了结构性质可建立递归关系如下：7=0,J=0i,J>0;X]=yji,J>0;X]Hyj0c_i}[j]=
