最长公共子序列问题.doc

《最长公共子序列问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验三最长公共子序列问题1.实验环境本实验采用java语言编写实现，环境：JDK1.8，编译器：eclipse2.实验目的通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。3.设计思路最长公共子序列的定义为：设有两个序列S1[1..m]和S2[1..n]，需要寻找它们之间的一个最长公共子序列。例如，假定有两个序列：S1：INTHEBEGINNINGS2：ALLTHINGSARELOST则S1和S2的一个最长公共子序列为THING。又比如：S1：ABCBDABS2：BDCABA则它们的一个最长

2、公共子序列为BCBA。这里需要注意的是，一个子序列不一定必须是连续的，即中间可被其他字符分开，单它们的顺序必须是正确的。另外，最长公共子序列不一定只有一个，而我们需要寻找的是其中一个。当然，如果要求子序列里面的元素必须连成一片也是可以的。实际上，连成一片的版本比这里实现的更容易。4.过程我们可以通过蛮力策略解决这个问题，步骤如下：1.检查S1[1..m]里面每一个子序列。2.看看其是否也是S2[1..n]里的子序列。3.在每一步记录当前找到的子序列里面最长的子序列。这种方法的效率十分低下。因此本实验采用

3、动态规划的方法实现该算法。利用动态规划寻找最长公共子序列步骤如下：1.寻找最长公共子序列的长度。2.扩展寻找长度的算法来获取最长公共子序列。策略：考虑序列S1和S2的前缀序列。设c[i，j]=

4、LCS(S1[1..i],S2[1..j])

5、，则有c[m，n]=

6、LCS(S1，S2)

7、所以有c[i–1，j–1]+1，如要S1[i]=S2[j]c[i，j]=max{c[i-1，j]，c[i，j-1]}，如果S1[i]≠S2[j]然后回溯输出最长公共子序列过程：5.实现源代码packagelcsimple;p

8、ublicclassLCSImplem{//返回一个决定搜索方向的数组privatestaticint[][]getLength(char[]stringArr1,char[]stringArr12){int[][]b=newint[stringArr1.length][stringArr12.length];int[][]c=newint[stringArr1.length][stringArr12.length];for(inti=1;i

9、j=1;j=c[i][j-1]){c[i][j]=c[i-1][j];b[i][j]=0;}//S1[i]≠S2[j]的情况else{c[i][j]=c[i][j-1];b[i][j]=-1;}}}returnb;}//回溯的

10、实现，采用递归法privatestaticvoidDisplay(int[][]b,char[]stringArr1,inti,intj){if(i==0

11、

12、j==0)return;if(b[i][j]==1){Display(b,stringArr1,i-1,j-1);System.out.print(stringArr1[i]+"");}elseif(b[i][j]==0){Display(b,stringArr1,i-1,j);}elseif(b[i][j]==-1){Display(b,stri

13、ngArr1,i,j-1);}}publicstaticvoidmain(String[]args){Stringstr1="ABCBDAB";Stringstr2="BDCABA";str1=""+str1;str2=""+str2;char[]stringArr1=str1.toCharArray();char[]stringArr2=str2.toCharArray();int[][]b=getLength(stringArr1,stringArr2);Display(b,stringArr1,s

14、tringArr1.length-1,stringArr2.length-1);}}6.断点调试及代码分析首先在main方法里定义两个字符串，如：对这两个字符串，使它们的第一个字符为空，即初始化之后的c[][]的第一行第一列，之所以要空出，是因为c[][]代表的是两个字符串数组多少个，0的意思就是某个字符串的长度为0。然后将这两个字符串分割为char型数组：接下来就调用getLength方法计算出决定搜索方向的数组，传到该方法的两个数组参数