作者在 2022-12-09 16:57:15 发布以下内容
我们知道：公共子序列是由一个个公共子串顺序连接而成的。为了求“最长公共子序列”，可以把字符串中的字分成2类：一类是要留下的（组成公共子串），另一类是要出列的。我们可以编程，把字符串（我取下面一行，txt2）从头到尾逐字鉴定该留还是该出列。
别看字符串五花八门、长长短短，鉴定起来却只有4种情况。而且并不是每一种都需要调用递归函数的。
我在【图一】中的每个公共子串的右面画一根蓝色竖线，表示原公共子串结束，新公共子串开始。
（下面所说的“情况一、情况二”，都可以用我们熟悉的、简单的编程语句来完成的。）
情况一：看第1个字“他”，上下2个字一样，“他”就留下，这情况我称为①。后面的字，只要还是在这个公共子串里，都可以这样来判断。
情况二：看第2根蓝色竖线后面的“啦”，它跟“了”不同，第1段公共子串结束。我们可以说，★所有的问题都是由公共子串结束引起的；所有的问题也只有1个：“谁是下一个公共子串的最优首字”。（引号里的14个字要多次用到，下文中用“F”来代替）“最优”什么意思？“最优”就是保证标题中的“最长”。
因为在“了”的右面再也找不到“啦”（我在程序里用Do 循环找），“啦”就出列。这情况我称为②。也不需要函数。
情况三：重点看下行第2条蓝线后面字“罗”，它与上面的“英”不同，却又能在“英白”的后面找到“罗”字，关键是“罗”左边的“英”能在下面“罗”的右面找到相同的“英”。这是“唯一问题”中的“唯一难点”。
★问：“罗”是不是“F”呢？或许“英”是的呢？★“是”还是“不是”的依据，就是能不能（在第2条蓝线后面全部的2个字符串）形成“最长公共子序列”。如果不是的话，“罗”就必须“出列”了。
这时必须要请“专家”（函数）了。这个专家有什么本事呢？它的工作就是★“求2个（首字一样的）字符串（字符串的末端就是整个字符串的末端）的最长公共子序列的字数”。我后面用（罗罗）、（英英）等来表示函数求出的值。
假定已经请到了“专家”。那么，解题的逻辑就很简单了。接下来的步骤和逻辑推理如下：
第一步，请“专家”（调用函数），计算（罗罗），（【图二】中是用2根粗红横线标出，我改用“（红红）”表示，更有代表性）。
第二步，用For循环顺序找到一对“英”、（一对“白”，假定可以找到），再请“专家”（调用函数）计算（英英）、（白白）……。我仿【图二】用（蓝蓝）来表示（英英）、（白白）……中的一个。
推理： ★如果始终没有 “（蓝蓝）>（红红）”，那么“罗”就是“F”，“罗”留下，★这样的情况我称为③1。
★如果一旦有（蓝蓝）,就是（英英）或（白白）>（罗罗）,那么“罗”就不是“F”了，这个推理是显而易见的。这时，“罗”必须“出列”；★这样的情况我称为③2。
（★想一想，这样的逻辑推理正确吗？关键是有了“最长”这个要求）
下行字符串txt2里的每一个字，都可以根据这4种情况（①、②、③1、③2）从左到右，逐字来判断“去”还是“留”的。我在【图一】里每个字的下面都标出来了。
关于“情况（①、②、③1、③2） ”。在我以前的博文中有比较详细的讲述。是很容易看懂的。
回过头来说“专家”，“专家”的解题思路就是我上文所叙述的思路。那么问题来了：既然“专家”也是这样的解题思路，那么，它在遇到情况③的时候，也要请个“助手”了。这个“助手”的名字及构造与“专家”（它的“上级”）是一模一样的，也要请新“助手”……★这在很多地方称为“自己调用自己”，（其实说“调用它的拷贝”更恰当）。这就是“递归”的“递”了。如果这样无穷“递”下去，问题还能解决吗？
仔细分析后发现，各个“助手”的工作内容会有很大的差别，关键是：最后总会迎来★“无需调用助手”、可以直接上交数据的那一刻（请读者试试分析最后一根蓝色竖线后面的2个字符串）。递归函数终归是可以开始“归”的。这样“上级”得到了“下级”传回的★数值（归），就可以继续工作而得到具体★数值，再交给自己的“上级”……，最后，邀请“专家”的那个程序（我们叫它“主程序”），就可以算出“最长公共子序列”的长度（字数）和“内容”了。
思考：前面的7个字（尤其是第5个字“，”），需要调用递归函数吗？为什么？下行字符串共19个字，只有“罗”字调用了递归函数，是吗？
几点说明：
1.程序主要由1个主程序和1个递归函数 LCS(a&,b&) 组成。这2部分的代码非常相似(★先看主过程的代码，后看函数的代码），因为它们的“任务”都是要“求出2个字符串的最长公共子序列”。主程序是对整个字符串（txt1、txt2、从头到尾，从左到右）进行求解。而递归函数是对“由主程序交代下来的两个部分的字符串”进行求解，且只求长度。交代下来的（参数）是：2个字符串的“首字”在整字符串txt1、txt2 中的位置（数值型数据）。而2个字符串的末端，分别都是 txt1 、txt2 的末端。（正因为如此，对太长的 txt1、txt2 求解会造成“（无响应）”）
2.两部分都有一个局部变量（名字一样，但是互不相干）Liu （留的音），它是因“情况③”引起的。当得到Liu=1时，表示判断结果是:这个字该“留”( ③1 ),它总是（下一个）公共子串的首字。当得到 Liu=0 时，表示判断结果是:这个字该“出列”( ③2 )。
3.为了减少读者的眼光在“文字”和“图片”之间反复跳转， 我在图片里加了文字说明，也有一些“推论”。其逻辑是否严密，敬请读者甄别。
4.★优化问题。如果每当需要计算“2个字符串的最长公共子序列的长度”时，就呼叫“助手”，“助手”还会呼叫“助手”……那工作量会“巨大”，因为这里有很多重复的计算。所以，这时应该先查一查★：“之前算过吗？有记录吗？”如果有的话，就不要呼叫“助手”了，直接拿来用就是了。（我用了一个“二维数组”---Zong()来记录），当元素的值不为零（大于零或者-1）时，表示这个元素已经算过了。反之，等于零时，要请“助手”（调用函数）。
5.大概是我的程序对“优化”做得不好，所以对于“长字符串”运算比较慢。我希望能得到帮助。
实验结果： （上传2组共4个文件。用其他编程语言编写的程序，也可以用它们来验证程序）
第一组：科学txt1.txt (約350字） ，科学txt2.txt (約350字），公共子序列长度是 327字（标准答案），时间 約5秒。
第二组：法txt1.txt (約1400字），法txt2.txt (約700字），公共子序列长度是 661字（标准答案），时间 約7分钟。
读者如果发现我这篇博文里有错误或者不妥，或者代码有错误和不妥，敬请指出，真诚感谢！如果有什么疑问，也请提出来，我会尽量解答。欢迎商榷和交流。
别看字符串五花八门、长长短短，鉴定起来却只有4种情况。而且并不是每一种都需要调用递归函数的。
我在【图一】中的每个公共子串的右面画一根蓝色竖线，表示原公共子串结束，新公共子串开始。
（下面所说的“情况一、情况二”，都可以用我们熟悉的、简单的编程语句来完成的。）
情况一：看第1个字“他”，上下2个字一样，“他”就留下，这情况我称为①。后面的字，只要还是在这个公共子串里，都可以这样来判断。
情况二：看第2根蓝色竖线后面的“啦”，它跟“了”不同，第1段公共子串结束。我们可以说，★所有的问题都是由公共子串结束引起的；所有的问题也只有1个：“谁是下一个公共子串的最优首字”。（引号里的14个字要多次用到，下文中用“F”来代替）“最优”什么意思？“最优”就是保证标题中的“最长”。
因为在“了”的右面再也找不到“啦”（我在程序里用Do 循环找），“啦”就出列。这情况我称为②。也不需要函数。
情况三：重点看下行第2条蓝线后面字“罗”，它与上面的“英”不同，却又能在“英白”的后面找到“罗”字，关键是“罗”左边的“英”能在下面“罗”的右面找到相同的“英”。这是“唯一问题”中的“唯一难点”。
★问：“罗”是不是“F”呢？或许“英”是的呢？★“是”还是“不是”的依据，就是能不能（在第2条蓝线后面全部的2个字符串）形成“最长公共子序列”。如果不是的话，“罗”就必须“出列”了。
这时必须要请“专家”（函数）了。这个专家有什么本事呢？它的工作就是★“求2个（首字一样的）字符串（字符串的末端就是整个字符串的末端）的最长公共子序列的字数”。我后面用（罗罗）、（英英）等来表示函数求出的值。
假定已经请到了“专家”。那么，解题的逻辑就很简单了。接下来的步骤和逻辑推理如下：
第一步，请“专家”（调用函数），计算（罗罗），（【图二】中是用2根粗红横线标出，我改用“（红红）”表示，更有代表性）。
第二步，用For循环顺序找到一对“英”、（一对“白”，假定可以找到），再请“专家”（调用函数）计算（英英）、（白白）……。我仿【图二】用（蓝蓝）来表示（英英）、（白白）……中的一个。
推理： ★如果始终没有 “（蓝蓝）>（红红）”，那么“罗”就是“F”，“罗”留下，★这样的情况我称为③1。
★如果一旦有（蓝蓝）,就是（英英）或（白白）>（罗罗）,那么“罗”就不是“F”了，这个推理是显而易见的。这时，“罗”必须“出列”；★这样的情况我称为③2。
（★想一想，这样的逻辑推理正确吗？关键是有了“最长”这个要求）
下行字符串txt2里的每一个字，都可以根据这4种情况（①、②、③1、③2）从左到右，逐字来判断“去”还是“留”的。我在【图一】里每个字的下面都标出来了。
关于“情况（①、②、③1、③2） ”。在我以前的博文中有比较详细的讲述。是很容易看懂的。
回过头来说“专家”，“专家”的解题思路就是我上文所叙述的思路。那么问题来了：既然“专家”也是这样的解题思路，那么，它在遇到情况③的时候，也要请个“助手”了。这个“助手”的名字及构造与“专家”（它的“上级”）是一模一样的，也要请新“助手”……★这在很多地方称为“自己调用自己”，（其实说“调用它的拷贝”更恰当）。这就是“递归”的“递”了。如果这样无穷“递”下去，问题还能解决吗？
仔细分析后发现，各个“助手”的工作内容会有很大的差别，关键是：最后总会迎来★“无需调用助手”、可以直接上交数据的那一刻（请读者试试分析最后一根蓝色竖线后面的2个字符串）。递归函数终归是可以开始“归”的。这样“上级”得到了“下级”传回的★数值（归），就可以继续工作而得到具体★数值，再交给自己的“上级”……，最后，邀请“专家”的那个程序（我们叫它“主程序”），就可以算出“最长公共子序列”的长度（字数）和“内容”了。
思考：前面的7个字（尤其是第5个字“，”），需要调用递归函数吗？为什么？下行字符串共19个字，只有“罗”字调用了递归函数，是吗？
几点说明：
1.程序主要由1个主程序和1个递归函数 LCS(a&,b&) 组成。这2部分的代码非常相似(★先看主过程的代码，后看函数的代码），因为它们的“任务”都是要“求出2个字符串的最长公共子序列”。主程序是对整个字符串（txt1、txt2、从头到尾，从左到右）进行求解。而递归函数是对“由主程序交代下来的两个部分的字符串”进行求解，且只求长度。交代下来的（参数）是：2个字符串的“首字”在整字符串txt1、txt2 中的位置（数值型数据）。而2个字符串的末端，分别都是 txt1 、txt2 的末端。（正因为如此，对太长的 txt1、txt2 求解会造成“（无响应）”）
2.两部分都有一个局部变量（名字一样，但是互不相干）Liu （留的音），它是因“情况③”引起的。当得到Liu=1时，表示判断结果是:这个字该“留”( ③1 ),它总是（下一个）公共子串的首字。当得到 Liu=0 时，表示判断结果是:这个字该“出列”( ③2 )。
3.为了减少读者的眼光在“文字”和“图片”之间反复跳转， 我在图片里加了文字说明，也有一些“推论”。其逻辑是否严密，敬请读者甄别。
4.★优化问题。如果每当需要计算“2个字符串的最长公共子序列的长度”时，就呼叫“助手”，“助手”还会呼叫“助手”……那工作量会“巨大”，因为这里有很多重复的计算。所以，这时应该先查一查★：“之前算过吗？有记录吗？”如果有的话，就不要呼叫“助手”了，直接拿来用就是了。（我用了一个“二维数组”---Zong()来记录），当元素的值不为零（大于零或者-1）时，表示这个元素已经算过了。反之，等于零时，要请“助手”（调用函数）。
5.大概是我的程序对“优化”做得不好，所以对于“长字符串”运算比较慢。我希望能得到帮助。
实验结果： （上传2组共4个文件。用其他编程语言编写的程序，也可以用它们来验证程序）
第一组：科学txt1.txt (約350字） ，科学txt2.txt (約350字），公共子序列长度是 327字（标准答案），时间 約5秒。
第二组：法txt1.txt (約1400字），法txt2.txt (約700字），公共子序列长度是 661字（标准答案），时间 約7分钟。
读者如果发现我这篇博文里有错误或者不妥，或者代码有错误和不妥，敬请指出，真诚感谢！如果有什么疑问，也请提出来，我会尽量解答。欢迎商榷和交流。
