6

我不明白 Knuth 在他对第 1.1 章练习 8 的说明中的意思。

任务是制作两个正整数的有效 gcd 算法，并m使用n他的符号theta[j],和其中 theta 和 phi 是字符串，并且- 在这种情况下代表计算步骤的正整数。phi[j]b[j]a[j]ab

让输入是表单的字符串a^mb^n。

schnaader 在这里给出了 Knuth 算法的一个很好的解释。

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

4

1 回答 1

7

当 Knuth 说“让输入由字符串表示a^mb^n”时，他的意思是输入应该采用mnumber of as 和nnumber of bs 的形式。因此输入f((m,n))wherem = 3和n = 2将由 string 表示aaabb。

花点时间回顾一下他在该章中的方程 3，它代表了一个马尔可夫算法。（以下）

        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（余数）替换为 |mn| 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然后添加 ac直到不再ab存在对。以我在顶部使用的示例为例，我们得到了这样操作的字符串aaabb, aab, caab, ca, cca, ccb, aab (then start again)

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

我希望这有帮助。实际上，我在我的博客上对马尔可夫算法的 Knuth 变体进行了更深入的分析。因此，如果您仍然感到有点卡住，请阅读该系列。

于 2015-01-30T23:22:09.227 回答