Knuth的计算机编程艺术 第1.1.8章节

Question

我无法理解Knuth在1.1章节中第8个练习中的指令的含义。

任务是使用他的符号theta[j]、phi[j]、b[j]和a[j]，使两个正整数m和n的最大公约数算法更加高效，其中theta和phi是字符串，a和b是正整数，表示此情况下的计算步骤。

输入为形式为a^mb^n的字符串。

schnaader在这里提供了关于Knuth算法的优秀解释。

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

- Maksim Bondaruk

---

这个问题可能更适合于程序员堆栈交换网站。 - Kohlbrr

我认为这里和cs.stackexchange.com上都可以。 - Simd

Answer 1

当Knuth说“让输入由字符串a^mb^n表示”时，他的意思是输入应该采用m个a和n个b的形式。因此，当m = 3且n = 2时，输入f((m,n))将由字符串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的值发生的输入字符串的情况。

现在，进入您的主要问题;

我的问题是如何将其与练习中给出的使用原始r（余数）替换为|m-n|和n替换为min（m，n）的E算法相连接。

基本上，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（然后重新开始）相同。当然，以上我们使用了模运算符和除法，但在上面的示例中，我们仅使用了减法。希望这可以帮助您。我实际上在我的博客上撰写了关于Knuth变异Markov算法的更深入分析。因此，如果您仍然感到有些困惑，请阅读该系列文章。

- Rudi Kershaw

Answer 2

所以，我尝试了一个解决方案，但如果可能的话，我希望能得到一些纠正。 根据Rudi的答案，对马尔可夫算法进行深入分析，并参考书中提供的提示，我为该字符串设计了以下一组转换规则，尽管它们并不是简单的转换。书中要求你尽量“简单”，而我猜检查m>n和m-n>0并不像马尔可夫算法所规定的那样简单，只进行字符串替换。但这仍然是一次尝试：

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^13 b^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)，显示了给定方向之间的关联，正如您在原始问题中所问。

- Pedro Henrique Bufulin