计算机编程艺术练习题：第 1 章，问题 8

Question

我正在做 TAOCP 第 1 卷第 3 版的练习，但无法理解以下练习的答案中使用的语法。

第一章练习8

计算正整数m & 的最大公约数 n 通过指定 T_j,s_j,a_j,b_j

让你的输入由字符串表示a^mbⁿ（m a 后面跟着 n 个 b）

答案：

设 A = {a,b,c}，N=5。 该算法将以字符串 a^gcd(m,n) 终止。

    j     Tj     sj    bj    aj
    0     ab  (empty)  1    2   Remove one a and one b, or go to 2.
    1   (empty)  c     0    0   Add c at extreme left, go back to 0.
    2     a      b     2    3   Change all a's to b's
    3     c      a     3    4   Change all c's to a's
    4     b      b     0    5   if b's remain, repeat

我无法理解的部分就是如何解释该表。 另外，当 Knuth 说这将以字符串 a^gcd(m,n) 终止时 - 为什么 gcd(m,n) 的上标？

谢谢你的帮助！

编辑了更多问题：

什么是 T_j - 请注意 T = Theta

什么是 s_j - 请注意 s = phi

如何解释列 b _j 和 a_j？

为什么 Knuth 将解决方案中的新符号转换为他在文本中没有解释的示例？ 只是令人沮丧。 谢谢！！！

Answer 1

这是该练习答案的实现。 也许有帮助。

顺便说一句，该表似乎描述了马尔可夫算法。

据我所知，到目前为止，您从第一个命令集 j = 0 开始。将所有出现的 T_j 替换为 s_j 并跳转到下一个命令行取决于您是否替换了任何内容（在这种情况下跳转到 b_j，如果没有替换任何内容，则跳转到 a_j）。

编辑：新答案：

A = {a,b,c} 似乎是您可以操作的字符集。 c 在算法过程中出现（添加到左侧，后来再次被 a 替换）。

Theta 和 phi 可能是您通常用于“原始”和“替换”之类的希腊字符，尽管我不知道它们是什么。

b_j 和 a_j 是接下来要执行的表行。 这与最后一栏中的人类可读的描述相匹配。

我唯一无法回答的是为什么 Knuth 在没有任何解释的情况下使用这个符号。 我又浏览了一遍书中的前几章和解决方案，他没有在任何地方提到这一点。

EDIT2：gdc(2,2) = 2 的示例

    Input string: aabb
    Line 0: Remove one a and one b, or go to 2.
    => ab => go to 1
    Line 1: Add c at extreme left, go back to 0.
    => cab => go to 0
    Line 0: Remove one a and one b, or go to 2.
    => c => go to 1
    Line 1: Add c at extreme left, go back to 0.
    => cc => go to 0
    Line 0: Remove one a and one b, or go to 2.
    No ab found, so go to 2
    Line 2: Change all a's to b's
    No a's found, so go to 3
    Line 3: Change all c's to a's
    => aa
    Line 4: if b's remain, repeat
    No b's found, so go to 5 (end).

    => Answer is "aa" => gdc(2,2) = 2

顺便说一句，我认为第 1 行的描述应该是“删除一个“ab”，或转到 2。” 这让事情变得更清楚了一些。

Answer 2

gcd(m,n) 的上标是由于该表中数字的表示方式决定的。

例如：m=> ^m
n => b^n

gcd(m,n) => a^gcd(m,n)

看起来像是正在实施欧几里得算法。
即，

gcd(m,n):
  if n==0:
    return m
  return gcd(n,m%n)

数字被表示为幂以便能够进行模运算m%n。

例如，4 % 3 将计算如下：
4 个'a' (a^4) mod 3'b's (b^3)，将留下 1 个'a' (a^1)。

Answer 3

a^m 的概念可能是状态机上下文中输入字符串的概念。

这样的概念用于指代连续 a 的 m 个实例，即：

a⁴ = aaaa
b⁷ = bbbbbbb
a⁴b⁷a³ = aaaabbbbbbbaaa

而 a^gcd(m,n) 的意思是运行后（解决方案）状态机，结果字符串应该是 a 的 gcd(m,n) 实例，

换句话说，a 的数量结果中的 应该等于 gcd(m,n) 的结果

我同意 @schnaader 的观点，因为它可能是一个描述马尔可夫算法用法的表。