《计算机编程艺术》练习题:第1章，第8个问题 [英] The Art of Computer Programming exercise question: Chapter 1, Question 8

问题描述

我正在对TAOCP第1版第3版进行练习，无法理解以下练习的答案中使用的语法.

I'm doing the exercises to TAOCP Volume 1 Edition 3 and have trouble understanding the syntax used in the answer to the following exercise.

第1章练习8

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

Computing the greatest common divisor of positive integers m & n by specifying T_j,s_j,a_j,b_j

让您的输入由字符串a ^m b ⁿ 表示(m a后跟n b)

Let your input be represented by the string a^mbⁿ (m a's followed by n b's)

答案:

让A = {a，b，c}，N = 5.该算法将以字符串a ^gcd(m，n)

Let A = {a,b,c}, N=5. The algorithm will terminate with the string 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)的上标?

The part that I have trouble understanding is simply how to interpret this table. Also, when Knuth says this will terminate with the string a^gcd(m,n) -- why the superscript for gcd(m,n) ?

感谢您的帮助！

编辑时有更多问题:

什么是T _j -请注意，T = Theta

What is T_j -- note that T = Theta

什么是s _j -请注意s = phi

What is s_j -- note that s = phi

您如何解释b _j 和a _j 列?

How do you interpret columns b_j and a_j?

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

Why does Knuth switch a new notation in the solution to an example that he doesn't explain in the text? Just frustrating. Thanks!!!

推荐答案

这是一个实现.也许有帮助.

Here's an implementation of that exercise answer. Perhaps it helps.

顺便说一句，该表似乎描述了 Markov算法.

By the way, the table seems to describe a Markov algorithm.

据我所知，您从第一个命令集j = 0开始.用s _j 替换T _j 的任何出现，然后跳转到下一个命令行，具体取决于您是否替换了任何内容(在这种情况下，请跳至b _j ，如果什么都没有被替换，请跳至a _j ).

As far as I understand so far, you start with the first command set, j = 0. Replace any occurencies of T_j with s_j and jump to the next command line depending on if you replaced anything (in that case jump to b_j, if nothing has been replaced, jump to a_j).

新答案:

A = {a，b，c}似乎是可以使用的字符集. c在算法执行过程中出现(添加到左侧，之后又被a替换).

A = {a,b,c} seems to be the character set you can operate with. c comes in during the algorithm (added to the left and later replaced by a's again).

Theta和phi可能是一些希腊字符，通常用于原始"和替换"之类的东西，尽管我不知道它们是什么.

Theta and phi could be some greek character you usually use for something like "original" and "replacement", although I wouldn't know they are.

b _j 和a _j 是接下来要执行的表行.这与上一列中易于理解的描述相符.

b_j and a_j are the table lines to be next executed. This matches with the human-readable descriptions in the last column.

我唯一无法回答的是为什么Knuth使用这种表示法而没有任何解释.我再次浏览了本书的第一章和解决方案，他没有在任何地方提及它.

The only thing I can't answer is why Knuth uses this notation without any explanations. I browsed the first chapters and the solutions in the book again and he doesn't mention it anywhere.

gdc(2,2)= 2的示例

Example for 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."这使事情变得更清楚.

By the way, I think description to line 1 should be "Remove one "ab", or go to 2." This makes things a bit clearer.

这篇关于《计算机编程艺术》练习题:第1章，第8个问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！