我无法理解 Knuth 在他对第 1.1 章练习 8 的说明中的意思。
任务是使用他的符号 theta[j] 对两个正整数 m 和 n 进行高效的 gcd 算法，phi[j]、b[j] 和 a[j] 其中 theta 和 phi 是字符串，a 和 b - 在这种情况下代表计算步骤的正整数。
令输入为 a^mb^n 形式的字符串。
schnaader 给出了 Knuth 算法的出色解释。 here .
我的问题是这如何与练习中给出的方向联系起来，使用书中给出的算法 E 将原始 r(余数)替换为 |m-n| 和 n 替换为 min(m,n)。
最佳答案
当 Knuth 说“让输入由字符串 a^mb^n 表示”时，他的意思是输入应该采用 m 数字的形式a 和 n 个 b。所以输入 f((m,n)) 其中 m = 3 和 n = 2 将由字符串 aaabb 表示。
花点时间回顾一下他在那一章中的等式 3，它代表一个 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 的值指定输入字符串会发生什么。
现在，开始您的主要问题；
My question is how this may be connected with the direction given in the excercise to use his Algorithm E given in the book with original r (remainder) substituted by |m-n| and n substituted by 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(然后重新开始)
这与 r = m % n, m = n, n = r(然后重新开始) 相同。不同之处当然是在上面我们使用了取模运算符和除法，而在上面的例子中我们只使用了减法。
希望对您有所帮助。我其实wrote a more in-depth analysis of Knuth's variation on a Markov algorithm在我的博客上。因此，如果您仍然觉得有点卡壳，请通读该系列。
关于algorithm - Knuth 计算机编程艺术 ex 1.1.8，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26742562/