1 写出最长公共子序列问题 最优子结构性质 2 写出最长公共子序列问题 求解递归式 3 设 X=( c, b, d, b), Y=( b, a, b, d, b, b) 写出c表格和b表格 写出最长公共子序列长度和最长公共子序列
时间: 2023-12-16 22:05:11 浏览: 27
好的,让我来回答您的问题。
1. 最长公共子序列问题(Longest Common Subsequence,LCS):给定两个序列X和Y,找到同时在两个序列中出现的最长子序列的长度。
最优子结构性质:设LCS(X,Y)表示序列X和Y的最长公共子序列,考虑X和Y的任意一个最长公共子序列Z,可以将Z分为两部分:Z'为Z去掉最后一个元素后得到的子序列,z为Z的最后一个元素。如果z在X和Y的LCS中,则LCS(X,Y)必然等于LCS(X',Y') + 1,其中X'和Y'为X和Y去掉最后一个元素后得到的子序列。否则,LCS(X,Y)等于LCS(X',Y)和LCS(X,Y')中的较大值。
2. 最长公共子序列问题的递归式:
设LCS(X,Y)表示序列X和Y的最长公共子序列的长度,则有:
LCS(X,Y) = 0,如果X或Y为空序列
LCS(X,Y) = LCS(X',Y') + 1,如果X和Y的最后一个元素相同
LCS(X,Y) = max(LCS(X',Y), LCS(X,Y')),如果X和Y的最后一个元素不相同
其中X'和Y'分别为X和Y去掉最后一个元素后得到的子序列。
3. 设X=(c,b,d,b),Y=(b,a,b,d,b,b),则c表格和b表格如下:
c表格:
| | b | a | b | d | b | b |
|---|---|---|---|---|---|---|
| c | 0 | 0 | 0 | 0 | 0 | 0 |
| b | 0 | 0 | 1 | 1 | 1 | 1 |
| d | 0 | 0 | 1 | 2 | 2 | 2 |
| b | 0 | 1 | 1 | 2 | 2 | 3 |
b表格:
| | b | a | b | d | b | b |
|---|---|---|---|---|---|---|
| c | | | | | | |
| b | | ↖ | ← | ↖ | ← | ↖ |
| d | | | ↖ | ← | ↖ | ← |
| b | | ↖ | ← | ↖ | ← | ↖ |
最长公共子序列的长度为3,一个可能的最长公共子序列为bdb。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.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)