Кнут Искусство компьютерного программирования ex 1.1.8

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

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

Пусть вход будет строкой вида a^mb^n,

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

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

Источник

2 ответа

Решение

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

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

        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 (остаток), замененным на | mn | и 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), Разница, конечно, в том, что в приведенном выше описании мы использовали оператор модуля и деление, но в приведенном выше примере мы использовали только вычитание.

Надеюсь, это поможет. На самом деле я написал более глубокий анализ вариации Кнута по алгоритму Маркова в моем блоге. Так что, если вы все еще чувствуете себя немного застрявшим, прочитайте сериал.

Источник

Итак, я попытался найти решение, но мне хотелось бы внести некоторые исправления, если это возможно. Основываясь на ответе Руди, углубленном анализе алгоритма Маркова и подсказках, представленных в книге, я достиг приведенного ниже набора правил перехода для строки, хотя это не простые переходы. Книги просят вас быть «как можно более простыми», и я думаю, проверяюm>nиm-n >0не так просто, как только подстановка строк, как это предписывает алгоритм Маркова. Но все же это попытка:

      1. a^m b^n -> a^(m-n) b^n, if m-n > 0;
2. a^0 b^n -> a^0 b^n, the algorithm ends and n is the answer;
3. a^m b^n -> a^n b^m, if n > m

это работает против a^13 b^3:

      f(a^13 b^3, 0) = (a^10 b^3, 1)
f(a^10 b^3, 1) = (a^7 b^3, 1)
... keep applying rule 1 until:
f(a^1 b^3, 1) = (a^3 b^1, 3)
f(a^3 b^1, 3) = (a^2 b^1, 1)
... keep applying rule 1 until:
f(a^0 b^1, 1) = (a^0 b^1, 2), 1 is the answer.  ∎

Кроме того, в моих правилах указаны подсказки |mn| и n <- min(m,n), показывая связь между заданным направлением, как вы задали в исходном вопросе.

Источник
Другие вопросы по тегам