1 / 9
文档名称:

最长公共子序列问题.doc

格式:doc   大小:424KB   页数:9页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

最长公共子序列问题.doc

上传人:知识改变命运 2022/11/26 文件大小:424 KB

下载得到文件列表

最长公共子序列问题.doc

文档介绍

文档介绍:该【最长公共子序列问题 】是由【知识改变命运】上传分享,文档一共【9】页,该文档可以免费在线阅读,需要了解更多关于【最长公共子序列问题 】的内容,可以使用淘豆网的站内搜索功能,选择自己适合的文档,以下文字是截取该文章内的部分文字,如需要获得完整电子版,请下载此文档到您的设备,方便您编辑和打印。实验三最长公共子序列问题
实验环境
本实验采纳java语言编写实现,环境:,编译器:eclipse
实验目的
经过最长公共子序列问题,稳固并详尽剖析动向规划思想和解题
步骤。
设计思路
最长公共子序列的定义为:设有两个序列S1[1..m]和S2[1..n],需要
找寻它们之间的一个最长公共子序列。
比如,假设有两个序列:
S1:INTHEBEGINNING
S2:ALLTHINGSARELOST
则S1和S2的一个最长公共子序列为THING。又比方:
S1:ABCBDAB
S2:BDCABA
则它们的一个最长公共子序列为BCBA。
这里需要注意的是,一个子序列不必定一定是连续的,即中间可
被其余字符分开,单它们的次序一定是正确的。此外,最长公共子序
列不必定只有一个,而我们需要找寻的是此中一个。
自然,假如要求子序列里面的元素一定连成一片也是能够的。实
际上,连成一片的版本比这里实现的更简单。
过程
我们能够经过蛮力策略解决这个问题,步骤以下:
检查S1[1..m]里面每一个子序列。
看看其能否也是S2[1..n]里的子序列。
在每一步记录目前找到的子序列里面最长的子序列。
这类方法的效率十分低下。所以本实验采纳动向规划的方法实现该算法。
利用动向规划找寻最长公共子序列步骤以下:
找寻最长公共子序列的长度。
扩展找寻长度的算法来获得最长公共子序列。
策略:考虑序列S1和S2的前缀序列。
设c[i,j]=|LCS(S1[1..i],S2[1..j])|,则有c[m,n]=|LCS(S1,S2)|
所以有
c[i–1,j–1]+1,如要S1[i]=S2[j]
c[i,j]=
max{c[i-1,j],c[i,j-1]},假如S1[i]≠S2[j]
而后回溯输出最长公共子序列过程:
实现源代码
packagelcsimple;
publicclassLCSImplem{
断点调试及代码剖析
第一在main方法里定义两个字符串,如:
对这两个字符串,使它们的第一个字符为空,即初始化以后的c[][]的第一行第一列,之所以要空出,是因为c[][]代表的是两个字符串数组多少个,0的意思就是某个字符串的长度为0。而后将这两个字符串切割为char型数组:
接下来就调用getLength方法计算出决定搜寻方向的数组,传到该方法的两个数组参数stringArr1和stringArr2的值能够看到
而后定义两个二维数组b[][],c[][],大小为*,用于接受结果矩阵。
接着遍历每一个stringArr1的值,与stringArr2的每一个值做比较:
循环内的第一层判断,就是当目前字符般配的时候,c[i][j]最为前缀序列为后边的般配计算使用,将目前值赋值为1,b[i][j]用于保留般配结果记为1:
把下边的两个判断作为第二层判断,即当目前字符不般配的时候
对c[i][j]做计算,c[i][j]就是该值在矩阵中上面一个数和左侧一个数中较大的值:
这些判断就是对该矩阵值的计算,c矩阵:
可是这个方法返回的是b矩阵,b矩阵在目前地点在字符般配时
的值为1,不般配时,就对c矩阵做出比较,该值在矩阵中左侧的数
值大于上面的数值时,b矩阵在目前地点在字符般配时的值为
0,反
之记为-1。所以,计算返回b矩阵,输出b矩阵
获得:
最后就是对结果的输出,对b矩阵调用Display方法:
当目前值为1时,说明字符般配成功,再对左上方的值进行比较;当目前值为0时,说明左侧的值大于上面的值,采纳递归法,再对上面的值进行比较;当目前值为-1时,对左侧的值进行比较。下边是对
的迭代:
这个方法,就是对下边矩阵方向的计算:
最后输出判断中般配上的结果。
算法剖析
因为每次调用起码向上或向左(或向上向左同时)挪动一步,故
最多调用(m*n)次就会碰到i=0或j=0的状况,此时开始返回。返回时与递归调用时方向相反,步数同样,故算法时间复杂度为Θ(m*n)。
实验结果
在main方法中输入的字符串为:
所以获得结果:
改变输入的字符串测试:
结果正确,实验结束。
实验总结
对最长公共子序列的求解,其实是对动向规划思想的学****这
个实验实现的算法比前两个实验实现的算法难度又有所提高,对字符
串进行频频递归时简单犯错,所以只好先对简单的字符串计算进行测
试。个人以为,动向规划思想中难的部分就是突出在频频的循环/递
归,对循环参数的取值常常让人伤神,需要十分慎重当心,并频频的
测试才能保证算法的正确性。

最近更新

2024年狼来了教学反思教学反思6篇 8页

2024年物理3-3教学反思精选7篇 23页

2024年物业保安小区工作总结5篇 60页

2024年父爱的作文600字5篇 8页

2024年父与子观后感500字作文参考5篇 7页

Mn掺杂ZnO稀磁半导体的制备与表征的任务书 2页

MiroSot足球机器人的路径规划研究的任务书 2页

MIMO系统中的天线选择与空时编码的中期报告 2页

2024年热门关于《三国演义》读后感参考范文4篇.. 6页

MD洗衣机供应链管理研究的中期报告 1页

MBEL600MW超临界机组锅炉特性分析的任务书 2页

2024年湘行二记的读后感7篇 10页

2024年游泳作文小学作文通用6篇 7页

Lucool涤纶氨纶针织物性能研究的中期报告 1页

2024年消防安全小学作文参考6篇 9页

Li-N-H储氢体系晶格动力学和电子结构的研究的.. 1页

LFMCW雷达信号处理技术研究的中期报告 1页

LCM企业构建MES的研究和实现的中期报告 2页

LAMOST输入星表中恒星与星系的分离的任务书 2页

K公司保健品营销策略研究的中期报告 2页

Kras基因对结肠癌转移相关蛋白调节机制的研究.. 2页

背调授权书模板 4页

冰箱采购合同范本 26页

泸州公租房申请条件 3页

英语试题双向细目表模板(范例) 2页

最新干部履历表最新(2022) 17页

2021年司法局机关办公室工作人员岗位职责 4页

航海学基础知识教学内容海图识图授课学时4日期.. 6页

准考证模版 2页

基督教对西方文明的影响 37页