当前位置：文档之家› 最长公共子序列实验报告

最长公共子序列实验报告

最长公共子序列问题

一．实验目的：

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){

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,charact

erString2,length1-1,length2-1)+1;

else

judge2[length1][length2]=max(searchLCS(characterString1,cha

racterString2,length1,length2-1),

searchLCS(characterString1,characterString2,length1-1,lengt

h2));

}

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，当两个数组的对应位置的字

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

时间复杂度公式：

代码实现：

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

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

五．实验感受：

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

多元时间序列建模分析

应用时间序列分析实验报告

单位根检验输出结果如下：序列x的单位根检验结果：

1967 58.8 53.4 1968 57.6 50.9 1969 59.8 47.2 1970 56.8 56.1 1971 68.5 52.4 1972 82.9 64.0 1973 116.9 103.6 1974 139.4 152.8 1975 143.0 147.4 1976 134.8 129.3 1977 139.7 132.8 1978 167.6 187.4 1979 211.7 242.9 1980 271.2 298.8 1981 367.6 367.7 1982 413.8 357.5 1983 438.3 421.8 1984 580.5 620.5 1985 808.9 1257.8 1986 1082.1 1498.3 1987 1470.0 1614.2 1988 1766.7 2055.1 1989 1956.0 2199.9 1990 2985.8 2574.3 1991 3827.1 3398.7 1992 4676.3 4443.3 1993 5284.8 5986.2 1994 10421.8 9960.1 1995 12451.8 11048.1 1996 12576.4 11557.4 1997 15160.7 11806.5 1998 15223.6 11626.1 1999 16159.8 13736.5 2000 20634.4 18638.8 2001 22024.4 20159.2 2002 26947.9 24430.3 2003 36287.9 34195.6 2004 49103.3 46435.8 2005 62648.1 54273.7 2006 77594.6 63376.9 2007 93455.6 73284.6 2008 100394.9 79526.5 run; proc gplot; plot x*t=1 y*t=2/overlay; symbol1c=black i=join v=none; symbol2c=red i=join v=none w=2l=2; run; proc arima data=example6_4; identify var=x stationarity=(adf=1); identify var=y stationarity=(adf=1); run; proc arima; identify var=y crrosscorr=x; estimate methed=ml input=x plot; forecast lead=0id=t out=out; proc aima data=out; identify varresidual stationarity=(adf=2); run;

最长公共子序列问题(最)

算法作业： LCS 问题作业要求：设计一个算法求出两个序列的所有LCS ，分析最坏情况，用“会计方法”证明利用b[i][j]求出所有LCS 的算法在最坏情况下时间复杂度为)(m m n C O + 1、算法思路：根据最长公共子序列问题的性质，即经过分解后的子问题具有高度重复性，并且具有最优子结构性质，采用动态规划法求解问题。设X={x 1, x 2, … , x n }, Y={y 1, y 2, … , y m }, 首先引入二维数组C[i][j]记录X i 和Y j 的LCS 的长度，定义C[i][j]如下： { j i j y i 且x ,i,j ]][j C[i j y i x j i j i C j i C j i C 00001110,]},1][[],][1[max{]][[===>+--≠>--=或，且为了构造出LCS ，还需要使用一个二维数组b[m][n]，b[i][j]记录C[i][j]是通过哪个子问题的值求得的，以决定搜索的方向，欲求出所有的LCS ，定义数组b 如下：设1-对角线方向;2-向上;3-向左;4-向上或向左若X[i]=Y[j],b[i][j] = 1, 若C[i-1][j][i][j-1], 则b[i][j] = 3, 若C[i-1][j]=[i][j-1], 则b[i][j] = 4, 根据以上辅助数组C 和b 的定义，算法首先需要求出这两个数组， C[m][n]中记录的最长公共子序列的长度，b 中记录了查找子序列元素的搜索方向。利用C 和b 的信息，Find_All_LCS 可以采用回溯法求出所有的LCS 。基本思路如下：使用一个辅助数组记录每次调用Find_All_LCS 得到的LCS 中的元素，每次递归调用一次Find_All_LCS ，进入一个新的执行层，首先要判断当前处理的两个子序列长度是否大于等于0 ，若不满足，则该层的递归结束，返回上一层；然后再判断当前得到的子序列是否等于数组C 中求出的最长公共子序列长度，若等于，则说明算法执行到此已经得到一个LCS ，按序输出；若不等于，此时根据数组b 中记录的搜索方向继续搜索，特别要说明的是，当b[i][j]=4时，即要向上或向左，需要对这两个方向分别调用Find_All_LCS ，保证沿着这两个方向上LCS 元素不被漏掉，都可以搜索到；若b[i][j]=1，即沿对角线方向搜索前进时，此时元素X[i]为LCS 中的元素，存放至辅助数组中去，同时将当前已经求得的LCS 长度增1，当递归调用Find_All_LCS 从b[i][j]=1处时，需要回溯一步，搜索其它路径上可能为LCS 中的元素。当所有的可能路径都已经搜索完，算法结束。对于某些情况会输出重复的LCS ，这是因为算法在沿不同路径搜索时可能会出现相同的LCS 序列。 2、时间复杂度分析由上述对Find_All_LCS 算法的分析可知，求出所有的LCS 实际上是根据搜索的方向信息遍历所有的路径找出满足条件的元素集合。因此，除求解辅助数组C 和b 所用的O(mn+m+n)的执行时间外，Find_All_LCS 的时间复杂度取决于所遍历路径数。而路径数是由搜索方向决定的。显然算法在最好的情况下，即m=n 并且b 中所有的值都指示沿着对角线方向搜索，时间复杂度为O(n). 相反，当X 和Y 序列不存在公共子序列时为算法的最坏情况，此时C 中所有值都等于0，数组b 中所有的值都指示要分别沿两个不同的方向（向左或向上）搜索，这种情况下每处理一次X[i],Y[j]时总是要沿两个方向分别调用Find_All_LCS ，遇到i=0或j=0时返回，直到搜索完所有的可能路径才结束，最坏情况下的搜索矩阵如下图所示：