穷举法求最长公共子序列c语言
时间: 2024-03-30 10:31:11 浏览: 23
根据提供的引用内容,穷举法求最长公共子序列的C语言实现如下[^1]:
```c
#include<stdio.h>
#include<string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(char *X, char *Y, int m, int n) {
if (m == 0 || n == 0)
return 0;
if (X[m - 1] == Y[n - 1])
return 1 + lcs(X, Y, m - 1, n - 1);
else
return max(lcs(X, Y, m, n - 1), lcs(X, Y, m - 1, n));
}
int main() {
char X[] = "ABCBDAB";
char Y[] = "BDCAB";
int m = strlen(X);
int n = strlen(Y);
printf("Length of LCS is %d\n", lcs(X, Y, m, n));
return 0;
}
```
该程序使用递归的方式实现了穷举法求解最长公共子序列的长度。在主函数中,我们定义了两个字符串X和Y,并计算它们的长度。然后,调用lcs函数来计算最长公共子序列的长度,并将结果打印出来。
相关问题
穷举法求最长公共子序列
穷举法是一种简单直观的求解问题的方法,它通过枚举所有可能的情况来找到最优解。在求解最长公共子序列(Longest Common Subsequence,简称LCS)的问题中,穷举法可以用来找到所有可能的子序列,并从中选取最长的一个作为结果。
穷举法求解最长公共子序列的步骤如下:
1. 首先,我们需要找到两个字符串的所有子序列。一个字符串的子序列是指从该字符串中删除0个或多个字符后得到的新字符串。
2. 然后,我们对两个字符串的所有子序列进行比较,找到它们之间相同的部分。
3. 最后,我们选择最长的相同部分作为最长公共子序列。
以下是穷举法求解最长公共子序列的示例代码:
```python
def find_lcs(str1, str2):
m = len(str1)
n = len(str2)
lcs = ""
max_length = 0
for i in range(2**m):
subsequence = ""
for j in range(m):
if (i >> j) & 1:
subsequence += str1[j]
if len(subsequence) > max_length and is_subsequence(subsequence, str2):
lcs = subsequence
max_length = len(subsequence)
return lcs
def is_subsequence(subsequence, string):
i = 0
j = 0
while i < len(subsequence) and j < len(string):
if subsequence[i] == string[j]:
i += 1
j += 1
return i == len(subsequence)
# 示例调用
str1 = "ABCD"
str2 = "ACDF"
lcs = find_lcs(str1, str2)
print("最长公共子序列为:", lcs)
```
C语言穷举法实现最长公共子序列
C语言中可以使用穷举法(也称为暴力法)来实现最长公共子序列(Longest Common Subsequence,简称LCS)。穷举法是一种简单但效率较低的算法,它通过遍历所有可能的子序列来找到最长公共子序列。
以下是C语言中使用穷举法实现最长公共子序列的示例代码:
```c
#include <stdio.h>
#include <string.h>
int max(int a, int b) {
return (a > b) ? a : b;
}
int lcs(char* str1, char* str2, int m, int n) {
if (m == 0 || n == 0) {
return 0;
}
if (str1[m - 1] == str2[n - 1]) {
return 1 + lcs(str1, str2, m - 1, n - 1);
} else {
return max(lcs(str1, str2, m, n - 1), lcs(str1, str2, m - 1, n));
}
}
int main() {
char str1[] = "ABCD";
char str2[] = "ACDF";
int m = strlen(str1);
int n = strlen(str2);
int result = lcs(str1, str2, m, n);
printf("最长公共子序列的长度为:%d\n", result);
return 0;
}
```
上述代码中,我们定义了一个递归函数`lcs`来计算最长公共子序列的长度。函数中使用了两个指针`m`和`n`来表示两个字符串的长度,通过比较字符是否相等来确定是否属于公共子序列。如果字符相等,则递归调用`lcs`函数,并将两个指针都向前移动一位;如果字符不相等,则分别递归调用`lcs`函数,一个指针向前移动一位,另一个指针保持不变。最后,返回两种情况中的较大值。
运行上述代码,将输出最长公共子序列的长度为3。