资源描述：
《最长公共子序列算法.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、《算法设计与分析》上机报告姓名：学号：日期：上机题目：最长公共子序列算法实验环境：CPU:2.10GHz;内存:6G;操作系统：Win764位;软件平台：VisualStudio2008;一、算法设计与分析：题目一:计算最优值给定两个序列X={x1,x2,......, xm}和Y={y1,y2,......,yn}，找出X和Y的最长公共子序列。一个给定序列的子序列是在该序列中删去若干个元素后得到的序列。给定两个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。例如，若X={A，B，C，B，D，
2、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和
3、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[][]，用c[i][j]记录X[i]与Y[j]的LCS的长度，b[i][j]记录c[i][j]是通过哪一个子问题的值求得的，以决定搜索的方向。我们是自底向上进行递推计算，那么在计算c[i,j]之前，c[i-1][j-1]，c
4、[i-1][j]与c[i][j-1]均已计算出来。此时我们根据X[i]=Y[j]还是X[i]!=Y[j]，就可以计算出c[i][j]。问题的递归式写成：题目二:构造最长公共子序列由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=和Y=的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i,j]中遇到"↖"时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i,j]中遇到"↑"时，表
5、示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i,j]中遇到"←"时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。二、核心代码：题目一:计算最优值//b[]=0左1左上2上voidLCS(charX[],intSizeX,charY[],intSizeY,int(*c)[SIZE_Y+1],int(*b)[SIZE_Y+1]){inti,j;for(i=0;i<=SizeX;i++)c[i][0]=0;for(j=0;j<=SizeY;j++)c[0][j]=0;for(i=1;i
6、<=SizeX;i++)for(j=1;j<=SizeY;j++){if(X[i-1]==Y[j-1]){c[i][j]=c[i-1][j-1]+1;b[i][j]=1;}elseif(c[i-1][j]>=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=2;}else{c[i][j]=c[i][j-1];b[i][j]=0;}}}题目二:构造最长公共子序列voidPrintLCS(charX[],int(*b)[SIZE_Y+1],inti,intj){if(0==i
7、
8、0==j)return;if(1
9、==b[i][j]){PrintLCS(X,b,i-1,j-1);cout<usingnamespacest
10、d;#defineSIZE_X7#defineSIZE_Y6//b[]=0左1左上2上voidLCS(charX[],intSizeX,charY[],intSizeY,int(*c)[SIZE_Y+1],int(*b)[SIZE_Y+1]){in
