knuth - 计算机编程艺术练习题 : Chapter 1, 问题 8

Question

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

第 1 章练习 8

通过指定 T_j,s_j,a_j,b _{计算正整数 m 和 n 的最大公约数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

这是一个implementation该练习的答案。也许有帮助。

顺便说一句，该表似乎描述了一个 Markov algorithm .

据我所知，到目前为止，您从第一个命令集 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 行。”这让事情变得更清楚了。