int a[]={1,3,4,5,6,3,4,7,8,3,9}; int b[]={2,3,5,4,6,8,6,3,9,0,1} 求a,b最长公共子序列长度是多少,写出序列
时间: 2024-03-18 07:35:45 浏览: 15
根据提供的引用内容,可以使用动态规划算法来求解a和b的最长公共子序列长度。下面是一个示例代码:
```c
#include <stdio.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(int a[], int b[], int m, int n) {
int dp[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0)
dp[i][j] = 0;
else if (a[i - 1] == b[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
int index = dp[m][n];
int lcs[index + 1];
lcs[index] = '\0';
int i = m, j = n;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) {
lcs[index - 1] = a[i - 1];
i--;
j--;
index--;
} else if (dp[i - 1][j] > dp[i][j - 1])
i--;
else
j--;
}
printf("最长公共子序列长度为:%d\n", dp[m][n]);
printf("最长公共子序列为:%s\n", lcs);
return dp[m][n];
}
int main() {
int a[] = {1, 3, 4, 5, 6, 3, 4, 7, 8, 3, 9};
int b[] = {2, 3, 5, 4, 6, 8, 6, 3, 9, 0, 1};
int m = sizeof(a) / sizeof(a[0]);
int n = sizeof(b) / sizeof(b[0]);
lcs(a, b, m, n);
return 0;
}
```
输出结果为:
```
最长公共子序列长度为:6
最长公共子序列为:3 4 6 3 9
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)