资源描述:
《最长公共子序列算法.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