用c语言写给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn},用动态规划算法找出X和Y的最长公共子序列
时间: 2024-05-10 18:14:20 浏览: 5
下面是用动态规划算法求解X和Y的最长公共子序列的C语言代码:
```c
#include <stdio.h>
#include <string.h>
#define MAX_LEN 100
int lcs(char X[], char Y[], int m, int n)
{
int L[m + 1][n + 1];
int i, j;
// 填充L[m + 1][n + 1]数组
for (i = 0; i <= m; i++) {
for (j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
L[i][j] = 0;
} else if (X[i - 1] == Y[j - 1]) {
L[i][j] = L[i - 1][j - 1] + 1;
} else {
L[i][j] = (L[i - 1][j] > L[i][j - 1]) ? L[i - 1][j] : L[i][j - 1];
}
}
}
return L[m][n];
}
int main()
{
char X[MAX_LEN];
char Y[MAX_LEN];
int m, n;
printf("请输入序列X:");
scanf("%s", X);
printf("请输入序列Y:");
scanf("%s", Y);
m = strlen(X);
n = strlen(Y);
printf("X和Y的最长公共子序列为:%d\n", lcs(X, Y, m, n));
return 0;
}
```
该程序中,我们使用一个二维数组L[m + 1][n + 1]来记录两个序列的最长公共子序列的长度。其中,L[i][j]表示序列X的前i个字符和序列Y的前j个字符的最长公共子序列的长度。我们可以根据以下公式来填充L[m + 1][n + 1]数组:
当i=0或j=0时,L[i][j]=0
当X[i-1]=Y[j-1]时,L[i][j]=L[i-1][j-1]+1
当X[i-1]!=Y[j-1]时,L[i][j]=max(L[i-1][j], L[i][j-1])
最后,我们返回L[m][n]作为X和Y的最长公共子序列的长度。