9

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

第 1 章练习 8

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

让您的输入由字符串 a m b n 表示（m a's 后跟 n b's）

回答：

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

    j T j      s j     b j     a j
    0 ab（空） 1 2 删除一个 a 和一个 b，或转到 2。
    1（空） c 0 0 在最左边添加 c，返回 0。
    2 ab 2 3 将所有 a 更改为 b
    3 ca 3 4 将所有 c 更改为 a
    4 bb 0 5 如果 b 剩余，重复

我难以理解的部分只是如何解释这张表。此外，当 Knuth 说这将以字符串 a gcd(m,n)结束时 ——为什么 gcd(m,n) 的上标？

谢谢你的帮助！

编辑了更多问题：

什么是 T j - 注意 T = Theta

什么是 s j - 注意 s = phi

您如何解释列 b j和 a j？

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

4

3 回答 3

4

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

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

据我目前了解，您从第一个命令集 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
    => 一个
    第 4 行：如果 b 仍然存在，则重复
    没有找到 b，所以转到 5（结束）。

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

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

于 2009-02-22T17:13:06.453 回答
1

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

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

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

看起来好像正在实施欧几里得算法。IE

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

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

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

于 2009-02-22T17:12:05.237 回答
1

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

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

a 4 = aaaa
b 7 = bbbbbbb
a 4 b 7 a 3 = aaaabbbbbbbaaa

而gcd(m,n)的意思是，在运行（解决方案）状态机之后，生成的字符串应该gcd(m,n)是a

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

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

于 2009-02-22T17:52:38.900 回答