实验二 最长公共子序列问题.docVIP

实验二 最长公共子序列问题 一、实验目的实验要求…,xm}和Y={y1,y2,…,yn}，找出X和Y的最长公共子序列。。 2、通过上机实验进行算法实现。保存和打印出程序的运行结果，并结合程序进行分析实验动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著Dynamic Programming，这是该领域的第一本著作。 2)与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是独立的。子问题中存在大量的公共子问题，在分治求解过程中被多次重复计算，保存计算结果，为后面的计算直接引用，减少重复计算次数这就是动态规划的基本思想。 3)用动态规划算法求解问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量重复计算，最终得到多项式时间算法。 动态规划基本步骤： 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 前三个步骤是动态规划算法的基本步骤。在只需求出最优值的情况，步骤四可以省去。若需要求最优解，则必须执行步骤四，根据所记录的信息，快速构造出最优解。 程序代码： #include iostream #include string #define N 20 using namespace std; int d[N][N]; int LCSlength(char* a,char* b,int c[][N]) { int i,j; int alen = strlen(a); int blen = strlen(b); for(i = 0; i = alen; i++) c[i][0] = 0; for(j = 0; j = blen; j++) c[0][j] = 0; for(i = 1; i = alen; i++) for(j = 1; j = blen; j++) if(a[i-1] == b[j-1]) c[i][j] = c[i-1][j-1] + 1; else c[i][j] = c[i][j-1] c[i-1][j]?c[i][j-1]:c[i-1][j]; return c[alen][blen]; } char *LCS(char *s,char* a,char* b) { int c[N][N]; int i = strlen(a); int j = strlen(b); int k = LCSlength(a,b,c); s[k] = \0; while(k 0) { if(c[i][j] == c[i-1][j]) i--; else if(c[i][j] == c[i][j-1]) j--; else { s[--k] = a[i-1]; i--; j--; } } return s; } main() { char *s = new char[N]; char s1[N]; char s2[N]; cout请输入第一个字符串: ; cins1; cout请输入第二个字符串: ; cins2; cout最长的公共子序列为: LCS(s,s1,s2) 长度为: LCSlength(s1,s2,d)endl; delete s; } 五、结果运行与分析： 心得与体会： 本次实验通过动态算法解决最长公共子序列问题，对于求两个序列的一个最长公共子序列, LCSlength算法时间复杂性为0 (alen*blen) ,能够得到较满意的结果。但另一个方面, 这种算法在对c