算法2_B13040905.docVIP

PAGE  实 验 报 告 （2014 / 2015 学年 第 二 学期） 课程名称算法设计与分析实验名称动态规划法求解实验时间2015年5月12日指导单位南京邮电大学指导教师陈春玲 学生姓名侯利萍班级学号学院(系)计算机软件学院专 业软件工程 PAGE - 8 - 实 验 报 告 实验名称动态规划法求解指导教师陈春玲实验类型上机实验学时2实验时间2015.5.12实验目的和要求 内容：用动态规划法求解两序列的最长公共子序列 要求：理解动态规划法的算法思想，清楚用动态规划法寻找LCS的最优解的实施过程，能将输入的两组序列后在屏幕上显示它们的最长公共子序列。二、实验环境(实验设备) 计算机，Visual Stdio三、实验原理及内容 1、实验原理： 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,xm}和Y={y1,y2,……,yn}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 分析LCS问题特征可知，如果Z={z1,z2,……，zk}为它们的最长公共子序列，则它们一定具有以下性质： 若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列； 若xm≠yn且xm≠zk，则Z是Xm-1和Y的最长公共子序列； 若xm≠yn且zk≠yn，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若xm=ym，则进一步分解为求解两个（前缀）子字符序列Xm-1和Yn-1的最长公共子序列问题； 如果xm≠yn，则原问题转化为求解两个子问题，即找出Xm-1和Y的最长公共子序列与找出X和Yn-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列Xi={x1,x2,……,xi}和Yj={y1,y2,……,yj}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j0且xi=yj max{c[i][j-1],c[i-1][j]} i,j0且xi≠yj 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 编程定义LCS类，计算最长公共子序列的长度，并给出最长公共子序列： （注意：C语言中数组下标由0开始，而实际数据在一维数组a、b和二维数组是c、s中存放却是从小标为1处开始。） 类中数据成员主要有二维数组c和s用于动态规划法求解过程中保存子问题的求解结果，一维数组a和b用于存放来两个字符序列，m和n为两个字符序列中实际字符的个数。这些数据成员均应在LCS类的构造函数中进行初始化： 2、实验代码： #include iostream.h #includemath.h class LCS { public: LCS(int nx, int ny, char *a, char *b); int LCSLength(); void CLCS(); private: void CLCS(int i, int j); int **c, **s, m, n; char *x, *y; }; LCS::LCS(int nx, int ny, char *a, char