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

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

第 1 章练习 8

Computing the greatest common divisor of positive integers m & n by specifying T_j,s_j,a_j,b_j

Let your input be represented by the string a^mbⁿ (m a's followed by n b's)

Answer:

Let A = {a,b,c}, N=5. The algorithm will terminate with the string 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
  

The part that I have trouble understanding is simply how to interpret this table. Also, when Knuth says this will terminate with the string a^gcd(m,n) -- why the superscript for gcd(m,n) ?

谢谢你的帮助！

编辑了更多问题：

What is T_j -- note that T = Theta

What is s_j -- note that s = phi

How do you interpret columns b_j and a_j?

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

这是一个执行 http://readingtaocp.wordpress.com/2008/09/13/markov-algorithms-in-scala/该练习的答案。也许有帮助。

顺便说一句，该表似乎描述了一个马尔可夫算法 http://en.wikipedia.org/wiki/Markov_algorithm.

As far as I understand so far, you start with the first command set, j = 0. Replace any occurencies of T_j with s_j and jump to the next command line depending on if you replaced anything (in that case jump to b_j, if nothing has been replaced, jump to a_j).

编辑：新答案：

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

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

b_j and a_j are the table lines to be next executed. This matches with the human-readable descriptions in the last column.

我唯一无法回答的是为什么 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 行”。这让事情变得更清楚了一些。