最长公共子序列实验报告.docx

《最长公共子序列实验报告.docx》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

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

5、ring2,intlength1,intlength2,intjudge[][10000]){intresult[100][100];for(inti=0;i<=length1;i++)result[i][0]=0;for(intj=1;j<=length2;j++)result[0][j]=0;for(inti=1;i<=length1;i++){for(intj=1;j<=length2;j++){if(characterString1[i-1]==characterString2[j-1]){result[i][j]=result[i-1][j-1]+1;j

6、udge[i][j]=0;}elseif(result[i-1][j]>=result[i][j-1]){result[i][j]=result[i-1][j];judge[i][j]=1;}else{result[i][j]=result[i][j-1];judge[i][j]=-1;}}}}voidLCS(intjudge[][10000],char*characterString1,intlength1,intlength2){//得到最长公共子序列if(length1==0

7、

8、length2==0)return;3/4if(judge[length1][l

9、ength2]==0){LCS(judge,characterString1,length1-1,length2-1);record(characterString1[length1-1]);//存入文件cout<

10、顶向下计算