最长公共子序列实验报告

最长公共子序列问题

一． 实验目的：

1. 加深对最长公共子序列问题算法的理解，实现最长公共子序列问题的求解算法； 2. 通过本次试验掌握将算法转换为上机操作；

3. 加深对动态规划思想的理解，并利用其解决生活中的问题。 二． 实验内容：

1. 编写算法：实现两个字符串的最长公共子序列的求解；

2. 将输入与输出数据保存在文件之中，包括运行时间和运行结果； 3. 对实验结果进行分析。 三． 实验操作：

1. 最长公共子序列求解：

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

动态规划算法是自底向上的计算最优值。

计算最长公共子序列长度的动态规划算法LCS-Length以characterString1和characterString2作为输入，输出两个数组result和judge1，其中result存储最长公共子序列的长度，judge1记录指示result的值是由那个子问题解答得到的，最后将最终的最长公共子序列的长度记录到result中。

以LCS-Length计算得到的数组judge1可用于快速构造序列最长公共子序列。首先从judge1的最后开始，对judge1进行配对。当遇到“↖”时，表示最长公共子序列是由characterString1(i-1)和characterString2(j-1)的最长公共子序列在尾部加上characterString1(i)得到的子序列；当遇到“↑”时，表示最长公共子序列和characterString1(i-1)与characterString2(j)的最长公共子序列相同；当遇到“←”时，表示最长公共子序列和characterString1(i)与characterString2(j-1)的最长公共子序列相同。

如图所示：

时间复杂度公式：

代码实现：

void LCSLength(char* characterString1,char*

characterString2,int length1,int length2,int judge[][10000]){

int result[100][100];

for(int i=0;i<=length1;i++) result[i][0]=0; for(int j=1;j<=length2;j++) result[0][j] = 0; for(int i=1;i<=length1;i++){ for(int j=1;j<=length2;j++){

if(characterString1[i-1]==characterString2[j-1]){ result[i][j]=result[i-1][j-1]+1; judge[i][j]=0; }

else if(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; } } }

}

void LCS(int judge[][10000],char* characterString1,int length1,int length2){//得到最长公共子序列 if(length1==0||length2==0) return; if(judge[length1][length2]==0){

1 / 4

LCS(judge,characterString1,length1-1,length2-1); record(characterString1[length1-1]);//存入文件 cout<

else if(judge[length1][length2]==1)

LCS(judge,characterString1,length1-1,length2);

else LCS(judge,characterString1,length1,length2-1);

}

3. 备忘录算法实现：

备忘录算法是从顶向下计算最优解的思想，备忘录方法的控制结构与直接递归方法的控制结构相同，但备忘录方法用一个表格来保存已解决的子问题的答案，避免了相同问题的重复求解。 代码实现： int searchLCS(char* characterString1,char* characterString2,int

length1,int length2){

if(judge2[length1][length2]>-1) return judge2[length1][length2];

if(length1==0||length2==0) judge2[length1][length2]=0; else{

if(characterString1[length1-1]==characterString2[length2-1])

judge2[length1][length2]=searchLCS(characterString1,characterString2,length1-1,length2-1)+1;

else

judge2[length1][length2]=max(searchLCS(characterString1,characterString2,length1,length2-1),

searchLCS(characterString1,characterString2,length1-1,length2));

}

return judge2[length1][length2];

}

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<=length2;j++) judge2[i][j]=-1; return

searchLCS(characterString1,characterString1,length1,length2); }

4. 递归法：

设有字符串characterString1和characterString2，当两个数组的对应位置的字

2 / 4

符相同时，则直接求解下一个位置，当不同时取两种情况中的最大值。

时间复杂度公式：

代码实现：

int recursionLCS(int i,int j,int length1){

if(i>=length1||j>=length2) return 0;

if(characterString1[i]==characterString2[j]) return

1+recursionLCS(i+1,j+1);

else return

recursionLCS(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），由于在多次测量下不稳定，故不做具体展示。

得到上述情况是由于生成的字符串具有不确定性，以及代码的不完善，不能对大数据进行时间测量。 五． 实验感受：

本次实验对字符串的反复递归，对栈的操作经常发生访问冲突的错误，故只能才用少量的数据处理，并且当数据存放到文件中时，子函数和主函数对同一文件的操作有覆盖和不显示的问题，故创建了两个文本文件用于对实验结果的存放。

3 / 4

本文来源：https://www.bwwdw.com/article/ggnd.html