最长公共子序列实验报告

1、最长公共子序列问题一 实验目的：1. 加深对最长公共子序列问题算法的理解，实现最长公共子序列问题的求解算法；2. 通过本次试验掌握将算法转换为上机操作；3. 加深对动态规划思想的理解，并利用其解决生活中的问题。二 实验内容：1. 编写算法：实现两个字符串的最长公共子序列的求解；2. 将输入与输出数据保存在文件之中，包括运行时间和运行结果；3. 对实验结果进行分析。三 实验操作：1. 最长公共子序列求解：将两个字符串放到两个字符型数组中，characterString1和 characterString2 ，当characterString1m= characterString2m时，找出这两个

2、字符串m 之前的最长公共子序列 ， 然 后 在 其 尾 部 加 上 characterString1m ， 即 可 得 到 最 长 公 共 子 序 列 。 当 characterString1m characterString2m 时 ， 需 要 解 决 两 个 子 问 题 ： 即 找 出characterString1(m-1) 和 characterString2 的一个最长公共子序列及characterString1 和characterString2(m-1) 的一个最长公共子序列，这两个公共子序列中较长者即为 characterString1 和 characterString2 的

3、一个最长公共子序列。2. 动态规划算法的思想求解：动态规划算法是自底向上的计算最优值。计算最长公共子序列长度的动态规划算法LCS-Length 以characterString1和characterString2 作为输入，输出两个数组result 和 judge1 ，其中 result 存储最长公共子序列的长度，judge1 记录指示result 的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到result 中。以 LCS-Length计算得到的数组 judge1 可用于快速构造序列最长公共子序列。 首先从 judge1 的最后开始，对 judge1 进行配对。当遇到“”

4、时，表示最长公共子序列是 由 characterString1(i-1) 和 characterString2(j-1) 的 最 长 公 共 子 序 列 在 尾 部 加 上 characterString1(i) 得 到 的 子 序 列 ； 当 遇 到 “ ” 时 ， 表 示 最 长 公 共 子 序 列 和 characterString1(i-1) 与 characterString2(j) 的最长公共子序列相同；当遇到“”时，表示最长公共子序列和characterString1(i) 与 characterString2(j-1) 的最长公共子序列相同。如图所示：.时间复杂度公式：代码实现

5、：void LCSLength(char* characterString1,char* characterString2,int length1,int length2,int judge10000)int result100100;for(int i=0;i=length1;i+) resulti0=0;for(int j=1;j=length2;j+) result0j = 0;for(int i=1;i=length1;i+)for(int j=1;j=resultij-1)resultij=resulti-1j;judgeij=1;elseresultij=resultij-1;ju

6、dgeij=-1;void LCS(int judge10000,char* characterString1,intlength1,int length2)/得到最长公共子序列if(length1=0|length2=0) return;if(judgelength1length2=0).LCS(judge,characterString1,length1-1,length2-1);record(characterString1length1-1);/ 存入文件 cout-1) returnjudge2length1length2;if(length1=0|length2=0) judge2

7、length1length2=0; elseif(characterString1length1-1=characterString2length2-1)judge2length1length2=searchLCS(characterString1,charact erString2,length1-1,length2-1)+1;elsejudge2length1length2=max(searchLCS(characterString1,characterString2,length1,length2-1),searchLCS(characterString1,characterString

8、2,length1-1,lengt h2);return judge2length1length2;int memorizedLCS(char* characterString1,char* characterString2) int length1=strlen(characterString1);int length2=strlen(characterString2);for(int i=1;i=length1;i+)for(int j=1;j=length1|j=length2) return 0;if(characterString1i=characterString2j) retur

9、n1+recursionLCS(i+1,j+1);else returnrecursionLCS(i+1,j)recursionLCS(i,j+1)?recursionLCS(i+1,j):recursionLCS(i,j+1);5.穷举法：将数组 characterString1和characterString2两个字符串的所有字串求出，并将这些字串相互比较，直到找的最长公共子序列为止，当字符串的长度很长时，所要求取的子串序列相当多，故所开销的时间最多。四 实验结果分析：当输入字符串长度分别为（20,20 ），（ 34,78 ），（ 98,145 ）时，在动态规划算法、备忘录算法、递归算法得到的时间分别为（0,0,0 ），（ 0,16,22 ），（ 0,16,34 ），由于在多次测量下不稳定，故不做具体展示。得到上述情况是由于生成