我正在做 TAOCP 第 1 卷第 3 版的练习，并且无法理解以下练习的答案中使用的语法。
第 1 章练习 8
通过指定 Tj，sj，aj，bj来计算正整数 m ＆ amp;n 的最大公约数
让您的输入由字符串 ambn表示（m a 's 后跟 n b' s）
答案：
令 A = {a,b,c},N = 5。算法将以字符串 agcd (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）的上标？
感谢您的任何帮助！
编辑更多的问题：
什么是 Tj-注意 T = Theta
什么是 sj-注意 s = phi
如何解释列 bj和 aj？
为什么 Knuth 将解决方案中的新符号切换到他没有在文本中解释的示例?只是令人沮丧。谢谢!!!
这是该练习答案的implementation。也许有帮助。
顺便说一句，该表似乎描述了一个Markov algorithm。
根据我的理解，到目前为止，您从第一个命令集 j = 0 开始。用 sj替换 Tj的任何出现，并跳转到下一个命令行，具体取决于您是否替换了任何内容（在这种情况下跳转到 bj，如果没有替换，则跳转到j）。
编辑：新的答案：
A = {a，b，c} 似乎是你可以操作的字符集。c 在算法期间进入（添加到左侧，后来再次替换为 a）。
Theta 和 phi 可能是您通常用于“原始”和“替换”之类的希腊字符，尽管我不知道它们是。
bj和 aj是下一步要执行的表行。这与最后一列中的人类可读的描述相匹配。
我唯一不能回答的是为什么 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”。
gcd（m，n）的上标是由于在此表中如何表示数字。
例如：m = & gt;a ^ m n = & gt;b ^ n
gcd (m,n) = & gt;a ^ gcd (m,n)
它看起来像欧几里德算在实施。即
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）。
m的概念可能是状态机上下文中输入字符串的概念。
这样的概念用于指代连续a的m实例，即：
a4= aaaa
b7= bbbbbbb
a4b7a3= aaaaabbbbbbbbaa
而gcd（m，n）的意思是，在运行（解决方案）状态机之后，结果字符串应该是a的gcd(m,n)实例
换句话说，结果中a的数量应等于gcd(m,n)的结果
我同意 @ schnaader，因为它可能是一个描述马尔可夫算法用法的表。
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（76条）