最长公共子序列（动态规划）报告.doc
需积分: 10 65 浏览量
更新于2023-05-14
收藏 226KB DOC 举报
算法设计与分析实验报告，附已通过源码，供学习参考，共勉♪
目录摘要如下：
1.问题描述
2.实验目的
3.实验原理
4.实验设计
（包括输入格式、算法、输出格式）
5.实验结果与分析
（除了截图外，实验结果还用图表进行了分析）
6.结论
7.程序源码
实验六：最长公共子数列（动态规划）报告
2017061111 李静娴
1．问题描述
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定
序列
X={ }
，则另一序列
Z={
1 2
, ,...,
m
z z z
}
是
X
的子序列是指存在一个严格递增
的下标序列
{ }
，使得对于所有
j=1,2,
…
,k
有
=
。例如，序列
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={ }
和
Y={ }
，
要求找出
X
和
Y
的一个最长公共子序列。
2．实验目的
（1）熟悉动态规划算法，并学以致用
（2）熟练掌握最长公共子序列算法
3．实验原理
1.
问题解析：设
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={ }
和
Y={ }
的最长公共子序列为
Z={
1 2
, ,...,
m
z z z
}
。则有：
(1)
若 ，则 ，且 是 和 的最长公共子序列。
(2)
若 且 ，则
Z
是 和
y
的最长公共子序列。
(3)
若 且 ，则
Z
是
x
和 的最长公共子序列。
其中，
={ }
，
={ }
，
Zk-1={ }
。
2.
递推关系：用
c[i][j]
记录序列
Xi
和
Yj
的最长公共子序列的长度。其中
={ }
，
={ }
。当
i=0
或
j=0
时，空序列是 和 的最长公共子序列。此时，
c[i]
[j]=0
；当
i,j>0
，
=
时，
c[i][j]=c[i-1][j-1]+1
；当
i,j>0
，
!=
时，
c[i][j]=max{c[i][j-1],c[i-1]
[j]}
，由此建立递推关系如下：
下载后可阅读完整内容，剩余7页未读，立即下载
2022-05-08 上传
2022-05-07 上传
2020-01-12 上传
qq_42236488
- 粉丝: 4
- 资源: 17
我的内容管理
展开
最新资源
- SSM动力电池数据管理系统源码及数据库详解
- R语言桑基图绘制与SCI图输入文件代码分析
- Linux下Sakagari Hurricane翻译工作：cpktools的使用教程
- prettybench: 让 Go 基准测试结果更易读
- Python官方文档查询库，提升开发效率与时间节约
- 基于Django的Python就业系统毕设源码
- 高并发下的SpringBoot与Nginx+Redis会话共享解决方案
- 构建问答游戏：Node.js与Express.js实战教程
- MATLAB在旅行商问题中的应用与优化方法研究
- OMAPL138 DSP平台UPP接口编程实践
- 杰克逊维尔非营利地基工程的VMS项目介绍
- 宠物猫企业网站模板PHP源码下载
- 52简易计算器源码解析与下载指南
- 探索Node.js v6.2.1 - 事件驱动的高性能Web服务器环境
- 找回WinSCP密码的神器：winscppasswd工具介绍
- xctools：解析Xcode命令行工具输出的Ruby库
