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

Question

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

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

Вычислить наибольший общий делитель натуральных чисел m & n, указав T_j, s_j, a_j, b_j

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

Ответ:

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

    j Tj sj bj aj
    0 ab (пусто)  1    2 Удалите один a и один b или перейдите к 2.
    1   (пусто)  c     0    0 Добавьте c в крайнем левом углу, вернитесь к 0.
    2     a      b     2    3 Измените все a на b
    3     c      a     3    4 Измените все c на a
    4     b      b     0    5 если b остаются, повторите

Часть, которую мне трудно понять, заключается в том, как просто интерпретировать эту таблицу. Кроме того, когда Кнут говорит, что это закончится строкой 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

    Входная строка: aabb
    Строка 0: удалите один a и один b или перейдите к 2.
    => ab => перейти к 1
    Строка 1: добавьте c в крайнем левом углу, вернитесь к 0.
    => такси => перейти к 0
    Строка 0: удалите один a и один b или перейдите к 2.
    => c => перейти к 1
    Строка 1: добавьте c в крайнем левом углу, вернитесь к 0.
    => cc => перейти к 0
    Строка 0: удалите один a и один b или перейдите к 2.
    AB не найден, поэтому перейдите к 2
    Строка 2: изменить все а на б
    Не найден, поэтому перейдите к 3
    Строка 3: поменяйте все c на a
    => аа
    Строка 4: если b остаются, повторите
    Нет b не найден, поэтому перейдите к 5 (конец).

    => Ответ "aa" => gdc(2,2) = 2

Кстати, я думаю, что описание к строке 1 должно быть "Удалить один"ab"или перейти к 2". Это делает вещи немного яснее.

Answer 2

Верхний индекс для 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).

Answer 3

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

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

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

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

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

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