Knuth 计算机编程艺术 ex 1.1.8

我无法理解 Knuth 在第 1.1 章练习 8 的说明中的含义。

任务是制定一个有效的两个正整数的 gcd 算法m and n使用他的符号theta[j], phi[j], b[j] and a[j]其中 theta 和 phi 是字符串，a and b- 代表本例中计算步骤的正整数。

令输入为以下形式的字符串a^mb^n.

Knuth 算法的一个很好的解释是施纳德 https://stackoverflow.com/users/34065/schnaader here https://stackoverflow.com/questions/575215/the-art-of-computer-programming-exercise-question-chapter-1-question-8/575315?s=15%7C2.9207#575315.

我的问题是这如何与使用书中给出的算法 E 的练习中给出的方向联系起来r（余数）替换为|m-n| and n替换为min(m,n).

当 Knuth 说“让输入由字符串表示a^mb^n”，他的意思是输入应该采取以下形式m数量as and n数量bs。所以输入f((m,n)) where m = 3 and n = 2将由字符串表示aaabb.

花点时间回顾一下该章中的方程 3，它代表马尔可夫算法 http://en.wikipedia.org/wiki/Markov_algorithm。 （以下）

        f((σ,j)) = (σ,a_j)        if θ_j does not occur in σ
        f((σ,j)) = (αφ_jω,b_j)    if α is the shortest string for which σ = αθ_jω
        f((σ,N)) = (σ,N)

所以想法是定义每个变量的序列j, θ_j, φ_j, a_j & b_j。这样，使用上面的马尔可夫算法，您可以指定输入字符串会发生什么，具体取决于j.

现在，进入你的主要问题；

我的问题是，这如何与练习中给出的方向联系起来，以使用书中给出的算法E，并将原始r（余数）替换为|m-n|并且n被min(m,n)替代。

本质上，Knuth 在这里所说的是，你不能用上述马尔可夫算法进行除法。那么最接近除法的是什么？好吧，本质上我们可以从较大的数字中减去较小的数字，直到剩下余数。例如;

10 % 4 = 2与执行以下操作相同；

        10 - 4 = 6        Can we remove another 4? Yes. Do it again.
        6  - 4 = 2        Can we remove another 4? No. We have our remainder.

现在我们有了剩下的部分。这本质上就是他希望您对我们的输入字符串执行的操作，例如aaabb.

如果您仔细阅读了书后 Knuth 的建议答案并完成了几个示例，您会发现这本质上就是他通过删除配对所做的事情ab然后添加一个c直到不再有配对为止ab存在。以我在顶部使用的示例为例，我们可以对字符串进行这样的操作aaabb, aab, caab, ca, cca, ccb, aab (then start again)

哪个是相同的r = m % n, m = n, n = r (then start again)。当然，不同之处在于，在上面我们使用了模运算符和除法，但在上面的示例中我们只使用了减法。

我希望这有帮助。其实我写了一篇关于 Knuth 对马尔可夫算法的变体的更深入的分析 http://www.rudikershaw.com/articles/computationalmethod3在我的博客上。因此，如果您仍然感觉有点困难，请阅读该系列。