Вопрос об искусстве компьютерного программирования: глава 1, вопрос 8

Question

Я выполняю упражнения для TAOCP, том 1, издание 3, и мне сложно понять синтаксис, использованный в ответе на следующее упражнение.

Глава 1 Упражнение 8

Вычисление наибольшего общего делителя натуральных чисел m & n путем задания T _j , с _j , a _j , b _j

Пусть ваш ввод будет представлен строкой a ^m b ⁿ (m a, затем n b)

Ответ:

Пусть A = {a, b, c}, N = 5. Алгоритм завершится строкой a ^{gcd (m, n)}

    j     T<sub>j</sub>     s<sub>j</sub>    b<sub>j</sub>    a<sub>j</sub>
    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

Часть, которую мне трудно понять, заключается в том, как просто интерпретировать эту таблицу. Кроме того, когда Кнут говорит, что это будет заканчиваться строкой a ^{gcd (m, n)} - почему верхний индекс для gcd (m, n)?

Спасибо за любую помощь!

Отредактировано с большим количеством вопросов:

Что такое T _j - обратите внимание, что T = Theta

Что такое s _j - обратите внимание, что s = phi

Как вы интерпретируете столбцы b _j и a _j ?

Почему Кнут переключает новую запись в решении на пример, который он не объясняет в тексте? Просто расстраивает. Спасибо !!!

Answer 1

Вот реализация этого ответа на упражнение. Возможно, это поможет.

Кстати, таблица, кажется, описывает алгоритм Маркова .

Насколько я понимаю, вы начинаете с первого набора команд, j = 0. Замените все вхождения T _j на s _j и перейдите к следующей команде. линия в зависимости от того, что вы заменили (в этом случае перейдите к b _j , если ничего не было заменено, перейдите к _j ).

РЕДАКТИРОВАТЬ: Новые ответы:

A = {a, b, c} - это набор символов, с которым вы можете работать. c входит во время алгоритма (добавляется слева, а затем снова заменяется на a).

Тэта и фи могут быть некоторыми греческими персонажами, которых вы обычно используете для чего-то вроде «оригинал» и «замена», хотя я бы не знал, что это так.

b _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". Это проясняет ситуацию.

Answer 2

понятие ^m , вероятно, является понятием входной строки в контексте конечного автомата.

Такое понятие используется для обозначения m экземпляров последовательных a, т. Е .:

.

a ⁴ = aaaa
b ⁷ = bbbbbbb
a ⁴ b ⁷ a ³ = aaaabbbbbbbaaa

И что ^{gcd (m, n)} означает, что после запуска конечного автомата (решения) полученная строка должна быть gcd(m,n) экземпляров a

Другими словами, число a в результате должно быть равно результату gcd(m,n)

И я согласен с @schnaader в том, что это, вероятно, таблица, описывающая использование алгоритма Маркова.

Answer 3

Верхний индекс для gcd (m, n) связан с тем, как числа представлены в этой таблице.

Например: m => a ^ m n => 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).