再谈LCS(最长公共子序列)另一解法-----用实例分析主过程和递归函数的解题过程(图)。附新编程序(LCS-1.exe)和网上收集的例题。

默认分类 | 2020-09-10 15:52:21 | 阅读 968 次 | 评论(0)
    主过程与函数几乎一样:(请参考2个附图)
把A、B两个字符串中的B、按从头到尾的顺序,逐个在A中寻找相同的字。会有3种结果:
1.直接找到(流程图中的“A”),于是这个字可以加入“最长序列”,然后n1+1、n2+1。这2个数的递增,保证了“一一对应”和“不颠倒顺序”。
2.从n1直到L1(A串的长度)都没有相同的字(流程图中的“Q”),那么这个字排除,且N2+1,而n1不增加,这样也遵守了上面的2个原则。
3.在A串的“延后几个字”(n1+k,k是延后的字数)找到(流程图中的“E”),这是必须按“最长”原则来定夺的,这正是“疑点”。函数中的“>”就是由此引起的。
下面重点讲“第3种情况”:这时,需要在2个字符串A、B中正确的选出4个字符串,请看“流程图”中的2个“蓝色粗划线”和“红色粗划线”所标出的字符串。调用一次函数求出“红、红”的“最长公共子序列”。有了红红的结果后,再调用一次函数求出“蓝、蓝”的“最长公共子序列”,把2个“最长”比较,如果“蓝蓝>红红”,那么A中的这个字不能在此刻连线,还得再A里面继续找。如果在调用函数的计算里,直接可以得到数据(“10次函数调用图”中的3、4、6、7、9、10),也就是不再发生“第3种结果”,那函数就能返回计算的结果。如果又发生“第3种结果”(“10次函数调用图”中的1、2、5、8)就得再在深一层调用函数......。
附加说明:
1.上次附件中的“LCS.exe”有错误。新程序的“计算2”,表示:把A、B两个字符串中的A(计算1是用B)、按从头到尾的顺序,逐个......。2个结果长短应该一样,但是“序列的内容”及“调用函数的次数”会不一样。

2.网上收集的例子,我用这个新程序都试过了,没有发现错误。

补充一句:如果第3种情况,且得到(流程图中)“N”的结果(“10次函数调用”中“Y”的结果),该字符得到认可,重点是★n1=n1+i+1 ,n2=n2+1(见流程图---对+ 1)A串必须跳过那些“被抛弃的字符”。不可以再参加后面的“寻找”。这也是“序列”的要求。

本文作者在9月14日对“10次函数调用图”做了一些修改。纠正了几处写错的字母。(在第一次调用函数框的左下角S4的地方:abbcea改成abbeca)和第二次调用函数框(全框的4个数据都改了)。都在该图的左面。在这里,为我的粗心对读者表示歉意。

10次函数调用.png (上传于2020-09-14 09:00:41)
10次函数调用.png

流程图.png (上传于2020-09-10 15:52:21)
流程图.png

演示.png (上传于2020-09-10 16:05:51)
演示.png

文章评论,共0条
游客请输入验证码
浏览51812次
文章分类