没有合适的资源?快使用搜索试试~ 我知道了~
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说,若给定序列X= { x1, x2,…, xm},则另一序列Z= {z1, z2,…, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,…, ik},使得对于所有j=1,2,…,k有 Xij=Zj。例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列时,称Z是序列X和Y的公共子序列。例如,若X= { A, B, C, B, D, A, B}和Y= {B, D, C, A, B, A},则序列{B,C,A}是X和Y的一个公共子序列,序列{B,C,B,A}也是X和Y的一个公共子序列。而且,后者是X和Y的一个最长公共子序列,因为X和Y没有长度大于4的公共子序列。给定两个序列X= {x1, x2, …, xm}和Y= {y1, y2, … , yn},要求找出X和Y的一个最长公共子序列。
资源推荐
资源详情
资源评论
问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序
列。确切地说,若给定序列 X= { x1, x2,…, xm},则另一序列 Z= {z1,
z2,…, zk}是 X 的子序列是指存在一个严格递增的下标序列 {i1, i2,…, ik},
使得对于所有 j=1,2,…,k 有 Xij=Zj。例如,序列 Z={B,C,D,B}是序列
X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,7}。给定两
个序列 X 和 Y,当另一序列 Z 既是 X 的子序列又是 Y 的子序列时,称
Z 是序列 X 和 Y 的公共子序列。例如,若 X= { A, B, C, B, D, A, B}和
Y= {B, D, C, A, B, A},则序列{B,C,A}是 X 和 Y 的一个公共子序列,序
列{B,C,B,A}也是 X 和 Y 的一个公共子序列。而且,后者是 X 和 Y 的一
个最长公共子序列,因为 X 和 Y 没有长度大于 4 的公共子序列。给定
两个序列 X= {x1, x2, …, xm}和 Y= {y1, y2, … , yn},要求找出 X 和 Y 的一
个最长公共子序列。
问题解析:设 X= { A, B, C, B, D, A, B},Y= {B, D, C, A, B, A}。求 X,Y
的最长公共子序列最容易想到的方法是穷举法。对 X 的多有子序列,检
查它是否也是 Y 的子序列,从而确定它是否为 X 和 Y 的公共子序列。
由集合的性质知,元素为 m 的集合共有 2^m 个不同子序列,因此,穷
举法需要指数级别的运算时间。进一步分解问题特性,最长公共子序列
问题实际上具有最优子结构性质。
设序列 X={x1,x2,……xm}和 Y={y1,y2,……yn}的最长公共子序列为
Z={z1,z2,……zk}。则有:
(1)若 xm=yn,则 zk=xm=yn,且 zk-1 是 Xm-1 和 Yn-1 的最长公共子序列。
(2)若 xm!=yn 且 zk!=xm,则 Z 是 Xm-1 和 Y 的最长公共子序列。
(3)若 xm!=yn 且 zk!=yn,则 Z 是 X 和 Yn-1 的最长公共子序列。
其中,Xm-1={x1,x2……xm-1},Yn-1={y1,y2……yn-1},Zk-1={z1,z2……zk-1}。
递推关系:用 c[i][j]记录序列 Xi 和 Yj 的最长公共子序列的长度。其中,
Xi={x1,x2……xi},Yj={y1,y2……yj}。当 i=0 或 j=0 时,空序列是 xi 和 yj 的
最长公共子序列。此时,c[i][j]=0;当 i,j>0,xi=yj 时,
c[i][j]=c[i-1][j-1]+1;当 i,j>0,xi!=yj 时,
c[i][j]=max{c[i][j-1],c[i-1][j]},由此建立递推关系如下:
构造最优解:由以上分析可知,要找出 X={x1,x2,……xm}和
Y={y1,y2,……yn}的最长公共子序列,可以按一下方式递归进行:当 xm=yn
时,找出 xm-1 和 yn-1 的最长公共子序列,然后在尾部加上 xm(=yn)即可得
X 和 Y 的最长公共子序列。当 Xm!=Yn 时,必须解两个子问题,即找出
Xm-1 和 Y 的一个最长公共子序列及 X 和 Yn-1 的一个最长公共子序列。这
两个公共子序列中较长者为 X 和 Y 的最长公共子序列。设数组 b[i][j]记
录 c[i][j]的值由哪一个子问题的解得到的,从 b[m][n]开始,依其值在数
组 b 中搜索,当 b[i][j]=1 时,表示 Xi 和 Yj 的最长公共子序列是由 Xi-1 和
Yj-1 的最长公共子序列在尾部加上 xi 所得到的子序列。当 b[i][j]=2 时,表
示 Xi 和 Yj 的最长公共子序列与 Xi-1 和 Yj-1 的最长公共子序列相同。当
b[i][j]=3 时,表示 Xi 和 Yj 的最长公共子序列与 Xi 和 Yj-1 的最长公共子序
列相同。
代码如下:
[cpp] view plain copy
1. //3d3-1 最长公共子序列问题
2. #include "stdafx.h"
3. #include <iostream>
4. using namespace std;
5.
6. const int M = 7;
7. const int N = 6;
8.
9. void output(char *s,int n);
10. void LCSLength(int m,int n,char *x,char *y,int **c,int **b);
11. void LCS(int i,int j,char *x,int **b);
12.
13. int main()
14. {
15. //X={A,B,C,B,D,A,B}
16. //Y={B,D,C,A,B,A}
17. char x[] = {' ','A','B','C','B','D','A','B'};
18. char y[] = {' ','B','D','C','A','B','A'};
19.
20. int **c = new int *[M+1];
21. int **b = new int *[M+1];
22. for(int i=0;i<=M;i++)
23. {
24. c[i] = new int[N+1];
25. b[i] = new int[N+1];
26. }
27.
28. cout<<"序列 X:"<<endl;
29. output(x,M);
30. cout<<"序列 Y:"<<endl;
31. output(y,N);
剩余17页未读,继续阅读
资源评论
会的东西有点杂
- 粉丝: 742
- 资源: 230
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功