2022年最长公共子序列问题.pdf

《2022年最长公共子序列问题.pdf》由会员分享，可在线阅读，更多相关《2022年最长公共子序列问题.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验三最长公共子序列问题1. 实验环境本实验采用 java 语言编写实现，环境：，编译器： eclipse2. 实验目的通过最长公共子序列问题，巩固并详细分析动态规划思想和解题步骤。3. 设计思路最长公共子序列的定义为： 设有两个序列 S11.m和 S21.n，需要寻找它们之间的一个最长公共子序列。例如，假定有两个序列：S1：I N T H E B E G I N N I N GS2：A L L T H I N G S A R E L O S T则 S1和 S2的一个最长公共子序列为THING 。又比如：S1：A B C B D A BS2：B D C A B A则它们的一个最长公共子序列为B

2、CBA 。这里需要注意的是，一个子序列不一定必须是连续的，即中间可被其他字符分开，单它们的顺序必须是正确的。另外，最长公共子序列不一定只有一个，而我们需要寻找的是其中一个。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 1 页，共 9 页 - - - - - - - - - - 当然，如果要求子序列里面的元素必须连成一片也是可以的。实际上，连成一片的版本比这里实现的更容易。4. 过程我们可以通过蛮力策略解决这个问题，步骤如下：1. 检查 S11.m里面每一个子序列。2. 看看其是否也是S21.n里的子序列

3、。3. 在每一步记录当前找到的子序列里面最长的子序列。这种方法的效率十分低下。因此本实验采用动态规划的方法实现该算法。利用动态规划寻找最长公共子序列步骤如下：1. 寻找最长公共子序列的长度。2. 扩展寻找长度的算法来获取最长公共子序列。策略：考虑序列S1和 S2的前缀序列。设 ci，j = |LCS (S11.i,S21.j)| ，则有 cm，n = |LCS(S1 ，S2)|所以有c i 1 ， j 1 + 1，如要 S1i = S2jci，j = max c i - 1 ，j ，c i ，j -1 ，如果 S1iS2j然后回溯输出最长公共子序列过程：精品资料 - - - 欢迎下载 - -

4、- - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 2 页，共 9 页 - - - - - - - - - - 5. 实现源代码package lcsimple;public class LCSImplem 断点调试及代码分析首先在 main 方法里定义两个字符串，如：对这两个字符串，使它们的第一个字符为空， 即初始化之后的 c的第一行第一列， 之所以要空出，是因为c代表的是两个字符串数组多少个， 0 的意思就是某个字符串的长度为0。然后将这两个字符串分割为 char 型数组：精品资料 - - - 欢迎下载 - - - - - - - - - -

5、- 欢迎下载 名师归纳 - - - - - - - - - -第 3 页，共 9 页 - - - - - - - - - - 接下来就调用 getLength 方法计算出决定搜索方向的数组， 传到该方法的两个数组参数stringArr1 和 stringArr2 的值可以看到然后定义两个二维数组b ，c，大小为 *，用于接受结果矩阵。接着遍历每一个 stringArr1 的值， 与 stringArr2 的每一个值做比较：循环内的第一层判断，就是当当前字符匹配的时候，cij 最为前缀序列为后面的匹配计算使用，将当前值赋值为1，bij 用于保存匹配结果记为 1：精品资料 - - - 欢迎下载 -

6、 - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 4 页，共 9 页 - - - - - - - - - - 把下面的两个判断作为第二层判断，即当当前字符不匹配的时候对 cij做计算， cij 就是该值在矩阵中上面一个数和左边一个数中较大的值：这些判断就是对该矩阵值的计算，c 矩阵：但是这个方法返回的是b 矩阵，b 矩阵在当前位置在字符匹配时的值为 1，不匹配时，就对c 矩阵做出比较，该值在矩阵中左边的数值大于上边的数值时， b 矩阵在当前位置在字符匹配时的值为0，反精品资料 - - - 欢迎下载 - - - - - - - - - - -

7、 欢迎下载 名师归纳 - - - - - - - - - -第 5 页，共 9 页 - - - - - - - - - - 之记为 -1。因此，计算返回b 矩阵，输出 b 矩阵得到：最后就是对结果的输出，对b 矩阵调用 Display方法：当当前值为 1 时，说明字符匹配成功， 再对左上方的值进行比较；当当前值为 0 时，说明左边的值大于上边的值，采用递归法，再对上边的值进行比较； 当当前值为 -1 时，对左边的值进行比较。 下面是对b 的迭代：精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 6 页，共

8、9 页 - - - - - - - - - - 这个方法，就是对下面矩阵方向的计算：最后输出判断中匹配上的结果。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 7 页，共 9 页 - - - - - - - - - - 7. 算法分析由于每次调用至少向上或向左（或向上向左同时）移动一步，故最多调用 (m * n) 次就会遇到 i = 0 或 j = 0 的情况，此时开始返回。返回时与递归调用时方向相反，步数相同，故算法时间复杂度为(m * n)。8. 实验结果在 main 方法中输入的字符串为：所以得到结

9、果：改变输入的字符串测试：结果准确，实验结束。9. 实验总结对最长公共子序列的求解，实际上是对动态规划思想的学习，这个实验实现的算法比前两个实验实现的算法难度又有所提升，对字符精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 8 页，共 9 页 - - - - - - - - - - 串进行反复递归时容易出错， 所以只能先对简单的字符串计算进行测试。个人认为，动态规划思想中难的部分就是突出在反复的循环/递归，对循环参数的取值往往让人伤神，需要十分谨慎小心，并反复的测验才能确保算法的正确性。精品资料 - - - 欢迎下载 - - - - - - - - - - - 欢迎下载 名师归纳 - - - - - - - - - -第 9 页，共 9 页 - - - - - - - - - -