最长公共子序列实验报告

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

2、最长公共子序列，然后在其尾部加上characterString1m，即可得到最长公共子序列。当characterString1m工characterString2m时，需要解决两个子问题：即找出characterStringl(m-l)和characterString2的一个最长公共子序列及characterStringl和characterString2(m-1)的一个最长公共子序列，这两个公共子序列中较长者即为characterString1和characterString2的一个最长公共子序列。2.动态规划算法的思想求解：动态规划算法是自底向上的计算最优值。计算最长公共子序列长度的动态规

3、划算法LCS-Length以characterString1和characterString2作为输入，输出两个数组result和judgel，其中result存储最长公共子序列的长度，judgel记录指示result的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到result中。以LCS-Length计算得到的数组judge1可用于快速构造序列最长公共子序列。首先从judgel的最后开始，对judgel进行配对。当遇到时，表示最长公共子序列是由characterStringl(i-l)和characterString2(j-1)的最长公共子序列在尾部加上character

4、Stringl(i)得到的子序列；当遇到“f”时，表示最长公共子序列和characterStringl(i-l)与characterString2(j)的最长公共子序列相同；当遇到“”时，表示最长公共子序列和characterString1(i)与characterString2(j-1)的最长公共子序列相同。如图所示：0i二tl或者j二。1+也吨-1/1i5j>O5ai-bjmaxb-1J,-1JL；Ji5J>0,ai/b|j代码实现：voidLCSLength(char*characterString1,char*characterString2,intlength1,intl

5、ength2,intjudge10000)intresult100100;for(inti=0;i<=length1;i+)resulti0=0;for(intj=1;j<=length2;j+)result0j=0;for(inti=1;i<=length1;i+)for(intj=1;j<=length2;j+)if(characterString1i-1=characterString2j-1)resultij=resulti-1j-1+1;judgeij=0;elseif(resulti-1j>=resultij-1)resultij=resulti-1j

6、;judgeij=1;elseresultij=resultij-1;judgeij=-1;voidLCS(intjudge10000,char*characterString1,intlengthl,intlength2)/得到最长公共子序列if(length1=0|length2=0)return;if(judgelength1length2=0)LCS(judge,characterString1,length1-1,length2-1);record(characterString1length1-1);/存入文件cout<<characterString1length1-

7、1;elseif(judgelength1length2=1)LCS(judge,characterString1,length1-1,length2);elseLCS(judge,characterString1,length1,length2-1);3. 备忘录算法实现：备忘录算法是从顶向下计算最优解的思想，备忘录方法的控制结构与直接递归方法的控制结构相同，但备忘录方法用一个表格来保存已解决的子问题的答案，避免了相同问题的重复求解。代码实现：intsearchLCS(char*characterString1,char*characterString2,intlength1,intleng

8、th2)if(judge2length1length2>-1)returnjudge2length1length2;if(length1=0|length2=0)judge2length1length2=0;elseif(characterString1length1-1=characterString2length2-1)judge2length1length2=searchLCS(characterString1,characterString2,length1-1,length2-1)+1;elsejudge2length1length2=max(searchLCS(charact

9、erString1,characterString2,length1,length2-1),searchLCS(characterString1,characterString2,length1-1,length2);returnjudge2length1length2;intmemorizedLCS(char*characterString1,char*characterString2)intlength1=strlen(characterString1);intlength2=strlen(characterString2);for(inti=1;i<=length1;i+)for(

10、intj=1;j<=length2;j+)judge2ij=-1;returnsearchLCS(characterString1,characterString1,length1,length2);4. 递归法：设有字符串characterStringl和characterString2,当两个数组的对应位置的字符相同时，则直接求解下一个位置，当不同时取两种情况中的最大值。时间复杂度公式：LCSiJ)=bj呵工bj1-fLC5(z+1J+1)m(LCS(iJ4lLCS(i+1J)代码实现：intrecursionLCS(inti,intj,intlength1)if(i>=len

11、gth1|j>=length2)return0;if(characterString1i=characterString2j)return1+recursionLCS(i+1,j+1);elsereturnrecursionLCS(i+1,j)>recursionLCS(i,j+1)?recursionLCS(i+1,j):recursionLCS(i,j+1);5. 穷举法：将数组characterStringl和characterString2两个字符串的所有字串求出，并将这些字串相互比较，直到找的最长公共子序列为止，当字符串的长度很长时，所要求取的子串序列相当多，故所开销的时间最多。四实验结果分析：当输入字符串长度分别为(20,20),(34,78),(98,145)时，在动态规划算法、备忘录算法、递归算法得到的时间分别为(0,0,0),(0,16,22),(0,16,34