最长公共子序列算法.doc

算法设计与分析上机报告姓名：学号：日期：上机题目：最长公共子序列算法实验环境：CPU: 2.10GHz ; 内存: 6G ; 操作系统：Win7 64位 ;软件平台：Visual Studio2008 ;一、算法设计与分析：题目一:计算最优值给定两个序列X=x1,x2, .,xm 和Y=y1,y2, .,yn ，找出X和Y的最长公共子序列。一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X=A，B，C，B，D，A，B，Y= B，D，C，A，B，A，序列B，C，A是X和Y的一个公共子序列，序列B，C，B，A也是X和Y的一个公共子序列，且为最长公共子序列。最长公共子序列问题具有最优子结构性质。设序列X= x1,x2, .,xm 和Y= y1,y2, .,yn 的最长公共子序列为Z= z1,z2, .,zk，则（1） 若xm =yn ，则zk =xm =yn ，且Zk-1 是Xm-1 和Yn-1 的最长公共子序列。（2） 若xm !=yn 且zk !=xm ，则Z是Xm-1 和Y的最长公共子序列。（3） 若xm !=yn 且zk !=yn ，则Z是X和Yn-1 的最长公共子序列。其中，Xm-1 = x1,x2, .,xm-1 ；Yn-1 = y1,y2, .,yn-1；Zk-1 = z1,z2, .,zk-1。解法： 引进一个二维数组c，用cij记录Xi与Yj 的LCS 的长度，bij记录cij是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算ci,j之前，ci-1j-1，ci-1j与cij-1均已计算出来。此时我们根据Xi = Yj还是Xi != Yj，就可以计算出cij。问题的递归式写成：题目二:构造最长公共子序列 由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=和Y=的最长公共子序列。首先从bm,n开始，沿着其中的箭头所指的方向在数组b中搜索。当bi,j中遇到时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当bi,j中遇到时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当bi,j中遇到时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。二、核心代码：题目一:计算最优值/b = 0左 1左上 2上void LCS(char X,int SizeX,char Y,int SizeY,int (*c) SIZE_Y + 1 ,int (*b)SIZE_Y+1 )int i,j;for(i=0;i= SizeX;i+)ci0 = 0;for(j=0;j= SizeY;j+)c0j = 0;for(i=1;i=SizeX;i+)for(j=1;j= cij-1 )cij = ci-1j;bij = 2;elsecij = cij-1;bij = 0;题目二:构造最长公共子序列void PrintLCS( char X, int (*b)SIZE_Y+1, int i, int j )if( 0 = i | 0 = j )return;if( 1 = bij )PrintLCS(X,b,i-1,j-1);cout Xi-1;elseif( 2 = bij )PrintLCS(X,b,i-1,j);elsePrintLCS(X,b,i,j-1);三、结果与分析：由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用(m + n)次就会遇到i = 0或j = 0的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为(m + n)。附录（源代码）算法源代码（C+描述）#include using namespace std;#define SIZE_X 7#define SIZE_Y 6/b = 0左 1左上 2上void LCS(char X,int SizeX,char Y,int SizeY,int (*c) SIZE_Y + 1 ,int (*b)SIZE_Y+1 )int i,j;for(i=0;i= SizeX;i+)ci0 = 0;for(j=0;j= SizeY;j+)c0j = 0;for(i=1;i=SizeX;i+)for(j=1;j= cij-1 )cij = ci-1j;bij = 2;elsecij = cij-1;bij = 0;void PrintLCS( char X, int (*b)SIZE_Y+1, int i, int j )if( 0 = i | 0 = j )return;if( 1 = bij )PrintLCS(X,b,i-1,j-1);cout Xi-1;elseif( 2 = bij )PrintLCS(X,b,i-1,j);elsePrintLCS(X,b,i,j-1);int main()char Y = B,D,C,A,B,A,0;char X = A,B,C,B,D,A,B,0;cout X= X endlY= Y endlXY的最长公共子序列为：endl;int bSIZE_X+1SIZE