计算机编程艺术练习题:第1章,问题8

Question

我正在练习TAOCP第1版第3版,并且无法理解下面练习答案中使用的语法.

第1章练习8

通过指定T _j,s _j,a _j,b _j来计算正整数m&n的最大公约数

让你的输入用字符串a ^m b ^n表示(ma后跟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说这将以字符串^gcd(m,n)终止时 - 为什么^gcd(m,n)的上标？

谢谢你的帮助!

编辑了更多问题:

什么是T _j - 注意T = Theta

什么是S _Ĵ -注意,S =披

你如何解释列b _j和_j？

为什么Knuth在解决方案中将新的符号转换为他未在文中解释的示例？只是令人沮丧.谢谢!!!

Answer 1

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

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

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

编辑：新答案：

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

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

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

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

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

    输入字符串：aabb
    第0行：删除一个a和一个b，或者转至2。
    => ab => 转到 1
    第 1 行：在最左边添加 c，返回到 0。
    => 出租车 => 转到 0
    第0行：删除一个a和一个b，或者转至2。
    => c => 转到 1
    第 1 行：在最左边添加 c，返回到 0。
    => 抄送 => 转到 0
    第0行：删除一个a和一个b，或者转至2。
    没有找到 ab，所以转到 2
    第 2 行：将所有 a 更改为 b
    没有找到a，所以转到3
    第 3 行：将所有 c 更改为 a
    => AA
    第 4 行：如果 b 剩余，则重复
    没有找到 b，所以转到 5（结束）。

    => 答案是“aa” => gdc(2,2) = 2

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