Knuth the art of computer programming ex 1.1.8

Question

Я не могу понять, что знал Кнут в своих инструкциях по упражнению 8 из главы 1.1.

Задача состоит в том, чтобы сделать эффективный алгоритм НОД двух положительных целых чисел m и n используя его обозначения theta[j], phi[j], b[j] и a[j] где тета и фи являются строками и a и b - целые положительные числа, которые представляют собой вычислительные шаги в этом случае ,

Пусть ввод будет строкой формы a^mb^n.

Отличное объяснение алгоритма Кнута дается schnaaderhere.

Мой вопрос, как это может быть связано с направлением данной в упражнении, чтобы использовать его алгоритм E в книге с оригинальным r (остатком) замещен |m-n| и n замещен min(m,n).

Answer 1

Когда Кнут говорит: «Пусть входной представляется строкой a^mb^n», что он означает, что входной сигнал должен иметь форму m числа a с и n числа b с. Таким образом, вход f((m,n)), где m = 3 и n = 2 будет представлен строкой aaabb.

Найдите минутку, чтобы оглянуться на его уравнение 3 в этой главе, которое представляет собой Markov algorithm. (Ниже)

 f((σ,j)) = (σ,a_j)  if θ_j does not occur in σ 
     f((σ,j)) = (αφ_jω,b_j) if α is the shortest string for which σ = αθ_jω 
     f((σ,N)) = (σ,N) 

Поэтому идея заключается в том, чтобы определить последовательность для каждой переменной j, θ_j, φ_j, a_j & b_j. Таким образом, используя алгоритм Маркова, вы можете указать, что происходит с вашей входной строкой, в зависимости от значения j.

Теперь, чтобы перейти к основному вопросу;

Мой вопрос заключается в том, как это может быть связано с направлением, данным в упражнении, для использования его алгоритма E, указанного в книге с оригинальным r (остаток), замененным на | m-n | и n заменяется на min (m, n).

Суть в том, что Кнут говорит здесь, заключается в том, что вы не можете делать деление с помощью вышеуказанного алгоритма Маркова. Итак, что самое близкое к делению? Ну, по существу, мы можем вычесть меньшее число из большего числа, пока мы не останемся с остатком. Например;

10 % 4 = 2 - это то же самое, что делать следующее;

 10 - 4 = 6  Can we remove another 4? Yes. Do it again. 
     6 - 4 = 2  Can we remove another 4? No. We have our remainder. 

И теперь у нас есть наш остаток. Это, по сути, то, что он хочет, чтобы вы сделали с нашей входной строкой, например, aaabb.

Если прочитать предложенный ответ Кнута в конце книги и работать через пару примеров вы увидите, что это, по сути, что он делает, удаляя пару ab, а затем добавить c пока больше пара ab существовать.Взяв пример, который я использовал наверху, мы получаем, что строка обрабатывается как таковая aaabb, aab, caab, ca, cca, ccb, aab (then start again)

То же, что и r = m % n, m = n, n = r (then start again). Разница, конечно, в том, что в приведенном выше примере мы использовали оператор модуля и деление, но в приведенном выше примере мы использовали только вычитание.

Надеюсь, это поможет. Я на самом деле wrote a more in-depth analysis of Knuth's variation on a Markov algorithm в своем блоге. Поэтому, если вы все еще чувствуете себя немного застрявшим, прочитайте серию.