devc++最长公共子序列。给定两个序列, , 使用动态规划算法求X和Y的最长公共子序列。 要求: (1) 写出递归公式 (2) 分析采用哪种数据结构存储中间结果 (3) 分析求解顺序 (4) 写出算法伪码 (5) 分析算法复杂度 (6) 使用熟悉的编程语言实现算法 (7) 生成测试数据,测试算法的正确性和性能
时间: 2023-12-29 21:03:54 浏览: 31
1. 递归公式:
设LCS(i,j)表示序列X1,X2,...,Xi与序列Y1,Y2,...,Yj的最长公共子序列长度,则有:
LCS(i,j) = 0, i=0 or j=0
LCS(i-1,j-1)+1, Xi=Yj
max{LCS(i-1,j),LCS(i,j-1)}, Xi≠Yj
2. 中间结果存储:采用一个二维数组dp[i][j]存储LCS(i,j)的值。
3. 求解顺序:按照递推公式从小到大依次计算dp[i][j]的值。
4. 算法伪码:
function LCS(X,Y)
m ← length(X)
n ← length(Y)
dp ← 二维数组,大小为(m+1)×(n+1)
for i from 0 to m
dp[i][0] ← 0
for j from 0 to n
dp[0][j] ← 0
for i from 1 to m
for j from 1 to n
if X[i] = Y[j]
dp[i][j] ← dp[i-1][j-1] + 1
else
dp[i][j] ← max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
5. 复杂度分析:时间复杂度为O(mn),空间复杂度为O(mn)。
6. 实现代码:
```c++
#include <iostream>
#include <cstring>
using namespace std;
int LCS(char* X, char* Y) {
int m = strlen(X);
int n = strlen(Y);
int dp[m+1][n+1];
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (X[i-1] == Y[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
int main() {
char X[] = "ABCBDAB";
char Y[] = "BDCABA";
int lcs = LCS(X, Y);
cout << "LCS length: " << lcs << endl;
return 0;
}
```
7. 测试数据:
X="ABCD", Y="ABDC",期望输出2;
X="AGGTAB", Y="GXTXAYB",期望输出4;
X="ABCBDAB", Y="BDCABA",期望输出4。