《算法分析与设计实验二：动态规划法》由会员分享，可在线阅读，更多相关《算法分析与设计实验二：动态规划法（3页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计实验二：动态规划法 题目：用动态规划法实现求两序列的最长公共子序列。 程序代码 #include #include /memset需要用到这个库 #include using namespace std; int const MaxLen = 50; class LCS public: LCS(int nx, int ny, char *x, char *y) /对数据成员m、n、a、b、c、s初始化 m = nx; /对m和n赋值 n = ny; a = new charm + 2; /考虑下标为0的元素和字符串结束标记 b = new charn + 2; memset(a,
2、 0, sizeof(a); memset(b, 0, sizeof(b); for(int i = 0; i nx + 2; i+) /将x和y中的字符写入一维数组a和b中ai + 1 = xi; for(int i = 0; i ny + 2; i+) bi + 1 = yi; c = new intMaxLenMaxLen; /MaxLen为某个常量值 s = new intMaxLenMaxLen; memset(c, 0, sizeof(c); /对二维数组c和s中元素进行初始化 memset(s, 0, sizeof(s); int LCSLength(); /求最优解值（最长公共
3、子序列长度） void CLCS() /构造最优解（最长公共子序列） CLCS(m, n); /调用私有成员函数CLCS(int,int) private: void CLCS(int i, int j); int (*c)MaxLen, (*s)MaxLen; int m, n; char *a, *b; ; int LCS:LCSLength() for(int i = 1; i = cij - 1) /由ci-1j得到cij cij = ci - 1j; sij = 2; else /由cij-1得到cij cij = cij - 1; sij = 3; return cmn; /返回最
4、优解值 /构造最长公共子序列 void LCS:CLCS(int i, int j) if(i = 0 | j = 0) /终止条件 return; if(sij = 1) CLCS(i - 1, j - 1); cout ai; /输出最优解的当前分量 else if(sij = 2) CLCS(i - 1, j); else CLCS(i, j - 1); int main() int nx, ny; char *x = new charMaxLen, *y = new charMaxLen; cout Please input X: endl; scanf(%s, x); nx = strlen(x); cout Please input Y: endl; scanf(%s, y); ny = strlen(y); LCS lcs(nx, ny, x, y); cout The LCSLength of X and Y is: lcs.LCSLength() endl; cout The CLCS is: endl; lcs.CLCS(); cout endl; delete x; delete y; return 0; 实验结果 输入X序列：abcbdab 输入Y序列：bdcaba 最长公共子序列长度为：4 最长公共子序列为： Bcba 3 / 3
