LCS最长公共子序列计算程序的核心代码说明 附程序和VB源文件

程序的核心代码段说明图:
默认分类 | 2020-09-22 14:46 | 阅读 478 次 | 评论 0 条

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

主过程与函数几乎一样:(请参考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”),这是必须按“最长”原则来定夺的,这正是“疑点”。函数中的“>”就是由此引起的。 下面重...
默认分类 | 2020-09-10 15:52 | 阅读 599 次 | 评论 0 条

LCS“最长公共子序列”的另一解题思路(绕开 6 X 7 宫格)----附件有自编的程序

为什么这个程序既可以验证一些网上LCS论文中举出的“短字符例题”(图一),也可以对代码稍作更改后,在1秒内求出近千字的“(无提醒打错的)中文打字测验”文本的“正确字数”(图二)。相信你在看了我下面的的描述后,应该可以有所明白。 两个字串的“最长公共子序列”可以从这样的角度描述:有上下两个字串,把下字串从左到右每一个字在上面“找到相同的字”并“连线”。 有2个要求:1.连线不许交叉。2.连线数“最多”。于是,在两个字串中“剔除”了“无法连线”的字之后,剩下的字串就是“最长公共子序列”了。 ★连线有3种情况,2种非常简单,1...
默认分类 | 2020-09-03 12:40 | 阅读 617 次 | 评论 0 条
浏览48678次
文章分类