计算机程序设计艺术问题:第一章问题8

这里有一个 implementation 关于那个练习的答案。也许这有帮助。

顺便说一句,这张桌子似乎描述了 Markov algorithm .

据我所知,您从第一个命令集开始,j=0。替换T的任何事件 _J 用S _J 跳到下一个命令行取决于您是否替换了任何内容(在这种情况下跳到b _J ,如果没有替换任何内容,请跳到 _J )

编辑:新答案:

A=A、B、C似乎是可以操作的字符集。C在算法中出现(添加到左侧,然后再次替换为A)。

theta和phi可以是希腊字符,通常用于“原始”和“替换”,尽管我不知道它们是什么。

乙 _J 和A _J 下一步要执行的表行。这与最后一列中人类可读的描述相匹配。

我唯一不能回答的是为什么克努斯不用任何解释就使用了这个符号。我又浏览了书中的第一章和解决方案,他什么地方也没提到。

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=>a^m n=& gt;b^ n

gcd(m,n)=>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)。

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

这种概念是用来指 m 连续的实例 a ,即:

一 ^四 AAAA
乙 ^七 BBBBBB
一 ^四 乙 ^七 一 ^三 =aaaabbbbbaaa

什么? ^GCD(m,n) 意味着在运行(解决方案)状态机之后,生成的字符串应该是 gcd(m,n) 实例 一

也就是说, 一 结果中的应等于 GCD(m,n)

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