我不明白Knuth在第1.1章练习8的说明中是什么意思。
任务是使用他的符号theta[j]、phi[j]、b[j]和a[j]来制作两个正整数m和n的有效gcd算法，其中θ和phi是字符串，a和b是在这种情况下表示计算步骤的正整数。
让一个输入是形式为a^mb^n的字符串。
schnaader在这里给出了Knuth算法的一个很好的解释。
我的问题是这与练习中给出的使用他在书中给出的算法E的方向如何联系，其中原始r（余数）被|m-n|取代，n被min(m,n)取代。
当Knuth说"让输入用字符串a^mb^n表示"时，他的意思是输入应该采用m个as和n个bs的形式。因此，输入f((m,n))，其中m = 3和n = 2将由字符串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（余数）由|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在马尔可夫算法上的变化的更深入的分析。所以，如果你仍然觉得有点困，不妨通读一下这个系列。
因此，我尝试了一个解决方案，但如果可能的话，我希望进行一些更正。基于鲁迪的回答、对马尔可夫算法的深入分析以及书中提供的提示，我实现了下面这组字符串的转换规则，尽管它们不是简单的转换。书上要求你成为；尽可能简单"；并且我猜想检查CCD_ 32和CCD_。但这仍然是一次尝试：
1. a^m b^n -> a^(m-n) b^n, if m-n > 0;
2. a^0 b^n -> a^0 b^n, the algorithm ends and n is the answer;
3. a^m b^n -> a^n b^m, if n > m
它对a^13b^3:起作用
f(a^13 b^3, 0) = (a^10 b^3, 1)
f(a^10 b^3, 1) = (a^7 b^3, 1)
... keep applying rule 1 until:
f(a^1 b^3, 1) = (a^3 b^1, 3)
f(a^3 b^1, 3) = (a^2 b^1, 1)
... keep applying rule 1 until:
f(a^0 b^1, 1) = (a^0 b^1, 2), 1 is the answer. ∎
此外，我的规则指定了提示|m-n|和n<-min（m，n），显示给定方向之间的联系，正如您在原始问题中所问的那样。