Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 197
Текст из файла (страница 197)
(31.15) Использование уравнения (31.5) в комбинации с уравнениями (31.14) и (31.15) завершает доказательство. Алгоритм Евклида В книге Евклида "Начала" (около 300 г. до н.э.) описывается приведенный ниже алгоритм вычисления бсс1 (хотя на самом деле он может иметь более раннее происхождение). Алгоритм Евклида выражается в виде рекурсивной программы и непосредственно основан на теореме 31.9. В качестве входных данных в нем выступают произвольные неотрицательные целые числа а и Ь.
ЕоС~~(а, 6) 1 1с Ь=О 2 слеп геспгп а 3 еие гегпгп еосшп(6, а пюс1 ь) Часть Ч!1. Избранные темы 964 В качестве примера работы процедуры Еосыв рассмотрим вычисление величины кЫ(30, 21): Евсин(30, 21) = Еисыо(21, 9) = ЕОсшп(9, 3) = Еисыо(3, 0) =3. В приведенных выше выкладках мы видим три рекурсивных вызова процедуры Ерш п. Корректность процедуры Еисып следует из теоремы 31.9, а также из того факта, что если алгоритм во второй строке возвращает значение а, то Ь = 0, а из уравнения (31.9) следует, что ясс1 (а, 6) = ясс1 (а, 0) = а. Работа этого рекурсивного алгоритма не может продолжаться до бесконечности, поскольку второй аргумент процедуры всегда строго убывает при каждом рекурсивном вызове, и он всегда неотрицательный.
Таким образом, алгоритм Еисьпз всегда завершается и дает правильный ответ. Время работы алгоритма Евклида Проанализируем наихудшее время работы алгоритма Еосшп как функцию размера входных данных а и Ь. Без потери общности предположим, что а > Ь > О. Это предположение легко обосновать, если заметить, что если Ь > а > О, то в процедуре Еисшп(а, 6) сразу же производится рекурсивный вызов процедуры ЕОсьпз(Ь,а). Другими словами, если первый аргумент меньше второго, то алгоритм Еисып затрачивает один дополнительный вызов на перестановку аргументов и продолжает свою работу. Аналогично, если Ь = а > О, то процедура завершается после одного рекурсивного вызова, поскольку а пюд Ь = О.
Полное время работы алгоритма ЕОсыо пропорционально количеству выполняемых ею рекурсивных вызовов. В нашем анализе используются числа Фибоначчи Гы определяемые рекуррентным соотношением (3.21). Лемма 31.10. Если а > Ь > 1 и в результате вызова процедуры ЕОсьпз(а,Ь) выполняется к > 1 рекурсивных вызовов, то а > Гь+з и Ь > гь+т. Доказаляеиьсляво. Докажем лемму путем индукции по 1я. В качестве базиса индукции примем /с = 1. Тогда 6 > 1 = Гз и, поскольку а > Ь, автоматически выполняется соотношение а > 2 = Гз.
Поскольку Ь > (а пюй Ь), при каждом рекурсивном вызове первый аргумент строго больше второго; таким образом, предположение а > Ь выполняется при каждом рекурсивном вызове процедуры. Примем в качестве гипотезы индукции, что лемма справедлива, если произведено Й вЂ” 1 рекурсивных вызовов; затем докажем„что она выполняется, если Глава 31. Теоретико-числовые алгоритмы 965 произведено к рекурсивных вызовов. Поскольку и > О, то и Ь > О, и в процедуре Евсин(а, Ь) рекурсивно вызывается процедура Еисшп(Ь, а шос( Ь), в которой, в свою очередь, выполняется Ь вЂ” 1 рекурсивных вызовов. Далее, согласно гипотезе индукции, выполняются неравенства Ь > Рн+1 (что доказывает часть леммы) и (а п1ос1 6) > Р~.
Мы имеем Ь+ (а щось 6) = Ь+ (а — 1а/6) Ь) < а, поскольку из а > Ь > О следует (а/6) > 1. Таким образом, а > 6+ (а п1ос1 6) > Рь+~ + Р~ = Гр+з. Из этой леммы непосредственно следует сформулированная ниже теорема. Теорема 31.11 (Теорема Ламе (1.аше)). Если для произвольного целого числа /с > 1 выполняются условия а > 6 > 1 и Ь < гь+ы то в вызове процедуры Еисщп(а, 6) производится менее й рекурсивных вызовов. Н Можно показать, что верхняя граница теоремы 31.11 — лучшая из возможных.
Последовательные числа Фибоначчи — наихудшие входные данные для процедуры Еисшо. Поскольку в процедуре Еисщп(гз, гз) производится ровно один рекурсивный вызов и поскольку при 1с > 2 выполняется соотношение ге+1 щос( Гь = = гь 1 мы имеем (р"+1 Ю = Кс<~(Гь (Рь+1 щи г))) = ксг( (х с Таким образом, в процедуре Еисьпэ(Гь+ы гь) рекурсия осуществляется в точности й — 1 раз, что совпадает с верхней границей теоремы 31.11. Поскольку число Е~ приблизительно равно ф"/~/5, где ф — золотое сечение (1+ ~/5)/2, определенное уравнением (3.22), количество рекурсивных вызовов в процедуре Еисьцз равно О (1я 6).
(Более точная оценка предлагается в упражнении 31.2-5.) Отсюда следует, что если с помощью алгоритма Еисщп обрабатывается два 13-битовых числа, то в нем производится О (13) арифметических операций и О (13з) битовых операций (в предположении, что при умножении и делении 13-битовых чисел выполняется О (рз) битовых операций. Справедливость этой оценки предлагается показать в задаче 31-2). Развернутая форма алгоритма Евклида Теперь перепишем алгоритм Евклида так, чтобы с его помощью можно было извлекать дополнительную полезную информацию, в частности, чтобы вычислять целые коэффициенты х и у, для которых справедливо равенство Н = ясс1 (а, 6) = ах + Ьу.
(31.1б) Часть ЧП. Избранные темы Таблица 31.1. Пример работы алгоритма Ехтя вю Еисми с входными числами 99 н 78 а 6 1а/61 Н х у 14 Заметим, что числа х и у могут быть равными нулю или отрицательными. Эти коэффициенты окажутся полезными позже при вычислении модульных мультипликативных обратных значений.
В качестве ввода процедуры Ехтвьвю Еисив выступает пара неотрицательных целых чисел, а на выходе эта процедура возвращает тройку чисел (Н, х, у), удовлетворяющих уравнению (31.1б). Ехтнвю Еисцв(а,Ь) 1 ЫЬ=О 2 тпеп гетпгп (а, 1, 0) 3 (д', х', у') — Ехтечию Еисып(Ь, а апой Ь) 4 (с(, х, у) — (И', у', х~ — '1а/6) у') 5 геФпгп (д,х,у) Работа алгоритма Ехтеьвю Еисив по вычислению величины кой(99,78) проиллюстрирована в табл.
31.1. В каждой строке показан один уровень рекурсии: входные величины а и Ь, вычисленная величина 1а/6), а также возвращаемые величины Н, х и у. Возвращаемая тройка значений (Н, х, у) становится тройкой, которая используется в ходе вычислений на следующем, более высоком уровне рекурсии. В результате вызова процедуры Ехтньвю Висим(99, 78) возвращаются величины (3, — 11, 14), так что бей (99, 78) = 3 = 99 ( — 11) + 78.
14. Процедура Ехтввю Еисыо представляет собой разновидность процедуры Еисив. Строка 1 в ней эквивалентна проверке равенства значение 6 нулю в первой строке процедуры Еисып. Если Ь = О, то процедура Ехтачпеп Еисипэ в строке 2 возвращает не только значение с( = а, но и коэффициенты х = 1 и у = О, так что а = ах + Ьу. Если Ь ф О, то процедура Ехтеьвю Еисив сначала вычисляет набор величин (Ы', х', у'), таких что Н' = бей (6, а щось 6) и И~ = Ьх~ + (а птог1 Ь) у .
(31.17) Как и в процедуре Еисыо, в этом случае мы имеем д = бсс1(а, 6) = Н' = = бсс1 (6, а лют 6). Чтобы получить значения х и у, для которых выполняется 99 78 21 15 б 3 78 21 15 б 3 0 Глава 31. Теоретико-числовые алгоритмы 967 равенство И = ах + Ьу, сначала перепишем уравнение (31.17) с использованием равенств Ы = И' и (3.8): Н = Ьх'+ (а — 1а/61 Ь) у' = ау' + Ь (х' — 1а/6) у') . Таким образом, при выборе величин х = у' и у = х' — 1а/61 у' удовлетворяется уравнение Н = ах+ Ьу, что доказывает корректность процедуры ЕхтехРеп Ецсы0. Поскольку количество рекурсивных вызовов в процедуре ЕОсшп равно количеству рекурсивных вызовов в процедуре ЕхтБчпнп ЕисшР, время работы процедуры Еисшп с точностью до постоянного множителя равно времени работы процедуры Ехтвчпнз Еисшп.
Другими словами, при а > Ь > О количество рекурсивных вызовов равно О (18 6). Упражнения 31.2-1. Докажите, что из уравнений (31.11) и (31.12) следует уравнение (31.13). 3! .2-2. Вычислите величины (Н, х, у), которые возвращаются при вызове процедуры Ехтнмпнп Еисыв(899, 493). 31.2-3. Докажите, что для всех целых чисел а, lс и п выполняется соотношение 8сс1(а, п) = бсср(а+ Йп,п). 31.2-4. Перепишите алгоритм Еисшп в итеративном виде, с использованием памяти фиксированного объема (т.е. в ней должно храниться не более некоторого фиксированного количества целочисленных значений).
31.2-5. Покажите, что если а > Ь > О, то при вызове процедуры Еисыв(а, Ь) выполняется не более 1 + 1обфЬ рекурсивных вызовов. Улучшите эту оценку до 1 + 1о89 (Ь/8п1 (а, 6) ). 31.2-б. Какие значения возвращает процедура Ехтеюнп Еисшп(г),+ы Гь)? Докажите верность вашего ответа. 31.2-7. Определим функцию 8сд для более чем двух аргументов с помощью рекурсивного уравнения бсср (ао, аз,..., а„) = бсср (ао, 8сй (ам аз,..., а„)). Покажите, что значение этой функции не зависит от порядка ее аргументов. Покажите также, как найти целые числа хо,хы..., х„, такие что бсср(ао,ам...,а„) = аохо + а1х1+ "а„х„. Покажите, что количество операций деления, которые производятся в алгоритме, равно О (и + 18 (шах (ао, ам..., а„) ) ).
31.2-8. Определим наименьшее общее кратное (1еаз1 сопппоп пш1бр1е) и целых чисел аы аз,..., а„, обозначаемое 1ст (ад, аз,..., а ), как наименьшее неотрицательное целое число, кратное каждому из аргументов а;. Покажите, как эффективно вычислить величину 1стп (ам аз,..., а„), используя в качестве подпрограммы (двухаргументную) операцию 8сс1. 968 Часть Чй. Избранные темы 31.2-9. Докажите, что числа пы пз, пз и п4 попарно взаимно просты тогда и только тогда, когда ясд (г41г42, пзг44) = бой (п1пз) п2п4) 1.
Покажите, что справедливо более общее утверждение, согласно которому числа пы п2,... пь попарно взаимно просты тогда и только тогда, когда множество (18 Ц пар чисел, образованных из по взаимно простые. 31.3 Модульная арифметика Неформально говоря, модульную арифметику можно считать обычной арифметикой, вычисления в которой производятся над целыми числами, за исключением того, что если что-то нужно вычислить по модулю числа и, то любой результат х заменяется элементом множества (О, 1,..., п — 1), равным числу х по модулю и (т.е. х заменяется величиной х шос1 п). Описанной выше неформальной модели достаточно, если ограничиться операциями сложения, вычитания и умножения. Более формализованная модель модульной арифметики, которая будет представлена ниже, лучше описывается в терминах теории групп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
