算法设计-长公共子序列.doc

最长公共子序列(LCS)算法
算法要求及分析
1. 算法要求:利用b[i,j],设计一个算法求出全部的LCS;利用”会计方法”,分析所编算法的时间复杂度的最坏情况。
2. 算法分析:该部分思路同课件
算法详细设计
为了求出全部的LCS,需要设计两个功能函数:LCS_L和LCS_Output,函数LCS_L实现计算LCS长度及每个子问题的由来;函数LCS_Output用递归方法实现输出所有LCS。
具体设计实现思路:
声明全局变量二维动态数组C和b。数组C记录所要求的LCS的长度;数组b记录C[i,j]是通过哪一个子问题的值求得的。定义枚举类型记录不同的遍历方向。
用动态规划法实现功能函数LCS_L,得出数组C和b。
函数实现思路:首先动态分配和初始化二维数组C和b,然后计算出C和b。
根据X[i]和Y[j]的关系,计算得出C[i,j]:
若X[i]=Y[j],则执行C[i,j]←C[i-1,j-1]+1且b[i][j]=ual;
‚若X[i]!=Y[j],则分为三种情况:
若C[i-1,j]>C[i,j-1]则C[i,j]取C[i-1,j]且b[i][j]=up;
若C[i-1,j]<C[i,j-1]则C[i,j]取C[i,j-1]且b[i][j]=le;
若C[i-1,j]=C[i,j-1]则C[i,j]取C[i-1,j]且b[i][j]=uol;
根据C和b编写输出函数LCS_Output输出所有的LCS。函数实现思路:
设置变量cur_len记录当前的数组下标,变量len保存当前LCS数组的元素个数。依次扫描二维数组b,从最后一个开始,根据b的值来判断递归方向:
当b的值是ual时,LCS数组保存当前字符,len++,沿对角线递归(递归完成要回溯);len等于LCS的长度时即找到一个LCS序列并输出;
当b的值是up时,向上递归;
当b的值是le时,向左递归;
当b的值是uol时,要找出所有的LCS,故既要向左也要向上递归。
主函数给出不同的测试数据输出相应的最长公共子序列长度和所有的最长公共子序列。
算法流程图
开始
功能函数LCS_L详细流程图
开始
动态分配二维数组C和b
定义int型变量i,j
初始化数组C的第0行和第0列
i < m ?
N
j < n ?
Y N
比较两个序列的当前字符是否相等?
Y
Y
C[i][j]= C[i-1][j-1]+1;
b[i][j] = ual;
C[i-1][j] 与C[i][j-1]的关系?
N
大于等于小于
C[i][j] = C[i][j-1];
b[i][j] = le;
C[i][j] = C[i-1][j];
b[i][j] = uol;
C[i][j] = C[i-1][j];
b[i][j] = up;
结束
功能函数LCS_Output详细流程图开始
i >=0 && j>=0?
N
Y
len当前值等于LCS的长度?
输出一个LCS
Y
N
b[i][j] == ual ?
Y
记录当前值;
利用回溯方法,使i-1,j-1递归功能函数LCS_Output;
N
b[i][j] == up ?
Y
使i-1递归调用