lcs(X, Y, m, n-1)
时间: 2023-06-10 14:04:10 浏览: 64
这个问题似乎是个算法问题,可以参考动态规划中最长公共子序列(LCS)算法。LCS算法可以用来求两个序列的最长公共子序列,其中X和Y是两个序列,m和n分别代表它们的长度。而lcs(X, Y, m, n-1)是指通过去掉Y中最后一个元素,来求解序列X和缩短后的Y的最长公共子序列的算法。
相关问题
#include <stdio.h> #include <string.h> #define MAXLEN 100 int dp[MAXLEN][MAXLEN]; // DP 数组,存储当前最长公共子序列长度 int prev[MAXLEN][MAXLEN]; // 用于记录 DP 数组中选择的方向,用于回溯得到最长公共子序列 void print_lcs(char X[], int i, int j) { if (i == 0 || j == 0) return; // 递归边界 if (prev[i][j] == 1) { print_lcs(X, i-1, j-1); printf("%c", X[i-1]); // 输出当前字符 } else if (prev[i][j] == 2) { print_lcs(X, i-1, j); } else { print_lcs(X, i, j-1); } } void lcs(char X[], char Y[]) { int m = strlen(X); int n = strlen(Y); // 计算 DP 数组 for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; continue; } if (X[i-1] == Y[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; prev[i][j] = 1; // 向左上方 } else { if (dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; prev[i][j] = 2; // 向上方 } else { dp[i][j] = dp[i][j-1]; prev[i][j] = 3; // 向左方 } } } } // 输出最长公共子序列 printf("LCS is: "); print_lcs(X, m, n); printf("\n"); } int main() { char X[MAXLEN], Y[MAXLEN]; printf("请输入两个字符串X和Y:\n"); scanf("%s%s", X, Y); lcs(X, Y); return 0; }测试算法的正确性和性能
为了测试算法的正确性和性能,可以准备一些测试用例,包括特殊情况和一般情况,并且记录算法运行时间。以下是一个简单的测试代码:
```
#include <stdio.h>
#include <string.h>
#include <time.h>
#define MAXLEN 100
int dp[MAXLEN][MAXLEN];
int prev[MAXLEN][MAXLEN];
void print_lcs(char X[], int i, int j) {
if (i == 0 || j == 0) return;
if (prev[i][j] == 1) {
print_lcs(X, i-1, j-1);
printf("%c", X[i-1]);
} else if (prev[i][j] == 2) {
print_lcs(X, i-1, j);
} else {
print_lcs(X, i, j-1);
}
}
void lcs(char X[], char Y[]) {
int m = strlen(X);
int n = strlen(Y);
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
continue;
}
if (X[i-1] == Y[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
prev[i][j] = 1;
} else {
if (dp[i-1][j] >= dp[i][j-1]) {
dp[i][j] = dp[i-1][j];
prev[i][j] = 2;
} else {
dp[i][j] = dp[i][j-1];
prev[i][j] = 3;
}
}
}
}
printf("LCS is: ");
print_lcs(X, m, n);
printf("\n");
}
int main() {
char X[MAXLEN], Y[MAXLEN];
printf("请输入两个字符串X和Y:\n");
scanf("%s%s", X, Y);
clock_t start = clock();
lcs(X, Y);
clock_t end = clock();
printf("算法运行时间:%f秒\n", (double)(end - start) / CLOCKS_PER_SEC);
return 0;
}
```
这个测试代码首先读入两个字符串,然后计算最长公共子序列并输出,最后记录算法的运行时间。可以用不同的输入进行多次测试,观察算法的正确性和性能表现。
将它的输入格式要求改成在屏幕上输入两个序列X和Y,序列各元素数间都以一个空格分隔,输出格式不变#include<bits/stdc++.h> using namespace std; string X ; string Y ; vector<vector<int> > c; // 动态规划表 set<string> lcs; // set保存所有的LCS int lcs_length(int m, int n) { // 表的大小为(m+1)*(n+1) c = vector<vector<int> >(m+1,vector<int>(n+1)); for(int i=0; i<m+1; ++i) { for(int j=0; j<n+1; ++j) { // 第一行和第一列置0 if (i == 0 || j == 0) c[i][j] = 0; else if(X[i-1] == Y[j-1]) c[i][j] = c[i-1][j-1] + 1; else c[i][j] = max(c[i-1][j], c[i][j-1]); } } return c[m][n]; } void lcs_print(int i, int j, string lcs_str) { while (i>0 && j>0) { if (X[i-1] == Y[j-1]) { lcs_str.push_back(X[i-1]); // cout<<X[i-1]<<endl; --i; --j; } else { if (c[i-1][j] > c[i][j-1]) --i; else if (c[i-1][j] < c[i][j-1]) --j; else { lcs_print(i-1, j, lcs_str); lcs_print(i, j-1, lcs_str); return; } } } // cout<<lcs_str<<endl; reverse(lcs_str.begin(),lcs_str.end()); lcs.insert(lcs_str); } int main() { cin>>X>>Y; int m = X.length(); int n = Y.length(); int length = lcs_length(m, n); cout << "The length of LCS is " << length << endl; string str; lcs_print(m, n, str); set<string>::iterator it = lcs.begin(); for( ; it!=lcs.end(); it++) cout << *it << endl; return 0; }
好的,你的要求已经记录下来了。下面是修改后的代码:
```
#include<bits/stdc++.h>
using namespace std;
vector<vector<int> > c; // 动态规划表
set<string> lcs; // set保存所有的LCS
int lcs_length(string X, string Y, int m, int n) {
// 表的大小为(m+1)*(n+1)
c = vector<vector<int> >(m+1,vector<int>(n+1));
for(int i=0; i<m+1; ++i) {
for(int j=0; j<n+1; ++j) {
// 第一行和第一列置0
if (i == 0 || j == 0)
c[i][j] = 0;
else if(X[i-1] == Y[j-1])
c[i][j] = c[i-1][j-1] + 1;
else
c[i][j] = max(c[i-1][j], c[i][j-1]);
}
}
return c[m][n];
}
void lcs_print(int i, int j, string lcs_str) {
while (i>0 && j>0) {
if (X[i-1] == Y[j-1]) {
lcs_str.push_back(X[i-1]);
--i;
--j;
}
else {
if (c[i-1][j] > c[i][j-1])
--i;
else if (c[i-1][j] < c[i][j-1])
--j;
else {
lcs_print(i-1, j, lcs_str);
lcs_print(i, j-1, lcs_str);
return;
}
}
}
reverse(lcs_str.begin(),lcs_str.end());
lcs.insert(lcs_str);
}
int main() {
cin >> X >> Y;
int m = X.length();
int n = Y.length();
int length = lcs_length(X, Y, m, n);
cout << "The length of LCS is " << length << endl;
string str;
lcs_print(m, n, str);
set<string>::iterator it = lcs.begin();
for( ; it!=lcs.end(); it++)
cout << *it << endl;
return 0;
}
```
修改后的代码可以读取两个字符串 `X` 和 `Y`,并计算它们的最长公共子序列及其长度。输出格式不变,仍然是每行输出一个最长公共子序列。