Алгоритмы - построение и анализ (1021735), страница 198
Текст из файла (страница 198)
(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 п). Описанной выше неформальной модели достаточно, если ограничиться операциями сложения, вычитания и умножения. Более формализованная модель модульной арифметики, которая будет представлена ниже, лучше описывается в терминах теории групп. Конечные группы Грунин (8топр) (Я, 9) — это множество Я, для элементов которого определена бинарная операция 9, обладающая перечисленными ниже свойствами. 1. Замкнутость: для всех элементов а, Ь Е Я имеем а 9 Ь Е 5. 2.
Существование единицьп существует элемент е е Я, который называется единичным (Ыеппйу) элементом группы; для этого элемента и любого элемента а Е Я выполняется соотношение е 9 а = а 9 е = а. 3. Ассоциативность: для всех а, Ь, с е Я выполняется соотношение (а 9 Ь) 9 9 с = а 9 (Ь 9 с). 4. Существование обратного элемента: для каждого элемента а е Я существует единственный элемент ЬЕ Я (он называется обратным (шчегзе) к элементу а), такой что а 9 Ь = Ь 9 а = е. В качестве примера рассмотрим уже знакомую нам группу (2, +) целых чисел с операцией сложения: в ней единичный элемент — О, а обратный элемент к любому числу а — число — а.
Если группа (Я, 9) обладает свойсн4ваи каимун4ативности (сопшш1айче 1ав) а 9 Ь = Ь 9 а для всех а, Ь Е Я, то это абелевн груннв (аЪе11ап 8гопр). Если группа (Я, 9) удовлетворяет условию ~Я! < оо, т.е. количество ее элементов конечно, то она называется конечной (Йпйе 8гопр). Глава 31. Теоретико-числовые алгоритмы 969 Группы, образованные сложением и умножением по модулю С помощью операций сложения и умножения по модулю и, где и — положительное целое число, можно образовать две конечные абелевы группы. Эти группы основаны на классах эквивалентности целых чисел по модулю и, определенных в разделе 31.!.
Чтобы определить группу над множеством классов Е„, нужно задать подходящие бинарные операции, полученные путем переопределения обычных операций сложения и умножения. Операции сложения и умножения над Е„определить легко, поскольку классы эквивалентности двух целых чисел однозначно определяют класс эквивалентности их суммы или произведения. Другими словами, если авва'(шос)и) и 6= 6'(тос1и), то а + Ь = а' + Ь'(пюс)и), ссЬ = а'Ь'(пюс(и) . Таким образом, операций сложения и умножения по модулю и, которые мы обозначим как +„и „, определяются следующим образом: [а]„+„[6]и = [а+ 6]„, [а]„„[Ь]„= [аЬ]„.
(31.18) (Вычитание в Е„можно легко определить как [а]„— „[Ь]„= [а — Ь]„, однако с делением, как мы сможем вскоре убедиться, дело обстоит сложнее.) Эти факты подтверждают удобную общепринятую практику использования наименьшего неотрицательного элемента каждого класса эквивалентности как представительного при вычислениях в Е„. Сложение, вычитание и умножение над представителями классов выполняется как обычно, но затем каждый результат х заменяется соответствующим представителем класса эквивалентности (т.е. величиной х пюс1 и).
На основе определения операции сложения по модулю и определяется аддипсиепап гРУппа по модУлю и (асЫ111че 8гоиР шос1и1о и) (Есо +„). РазмеР аддитивной группы по модулю и равен ]Е„[ = и. В табл. 31.2 представлены результаты выполнения операций в группе (Еа, +а). Теорема 31.12. Система (Е„, +„) образует конечную абелеву группу. Дсоказапсгльспсво. Из уравнения (31.18) следует замкнутость группы (Е„, +„). Ассоциативность и коммутативность операции +„следует из ассоциативности Часть Ч!!. Избранные темы 970 и коммутативности операции +: ([а]„+„[Ь]„) +„[с)„= [а+ Ь]„+„[с]„= = [(а + 6) + с]„= = [а+ (Ь+ с))„= = [а]„+„[Ь+ с]„= = [а]„+„([6]„+„[с]„), [а)„+„[Ь]„= [а+ Ь]„= = [Ь+ а)„= = [6]„+„[а)„. В роли единичного элемента (Е„, +„) выступает 0 (т.е.
класс [0]„). Элемент, аддитивно обратный элементу а (т.е. классу [а) „), представляет собой элемент — а (те. класс [-а]„или [и — а]„), поскольку [а)„+„[ — а)„= [а — а]„= [0]„. ° На основе операции умножения по модулю и определяется мульюиплпквтивпап группа по модулю и (шп!!!р!!санте йгоир шест!о и) (Е„*,.„). Элементы этой группы образуют множество Е„', образованное из элементов множества Е„, взаимно простых с и: Е„' = ([а]„Е Е„: йсй (а, и) = Ц.
Чтобы убедиться, что группа Е„' вполне определена, заметим, что для 0 < а < и при всех целых !с выполняется соотношение а = (а+ !си) (шайи). Поэтому из йод(а, и) = 1, согласно результатам упражнения 3 1.2-3, для всех целых /с следует, что бей (а + ик, и) = 1. Поскольку [а]„= (а + )си: к Е Е), множество Е„' вполне определено. Примером такой группы является множество Е1ь — — (1, 2, 4, 7, 8, 11, 13, 14), в качестве групповой операции в которой выступает операция умножения по модулю 15. (Здесь элемент [а]„ь обозначается как а; например, элемент [7], обозначается как 7.) В табл. 31.3 показаны результаты выполнения операции для данной группы. Например, 8 .
11 аа 13 (шой15). Единичным элементом в этой группе является 1. Теорема 31.13. Система (Е,"„„) образует конечную абелеву группу. Доказаюельсиюво. Замкнутость (Е„',;,) следует из теоремы 3!.б. Ассоциативность и коммутативность для операции;, можно доказать аналогично доказательству этих свойств для операции +„в теореме 3 !.12. В роли единичного здесь Глава 31. Теоретико-числовые алгоритмы 971 Таблица 31.2. Группа (Еа, +а) Таблица 31.3. Группа (Я~м и) выступает элемент [1]„. Чтобы показать наличие обратных элементов, предположим, что а — элемент множества Е„*, а набор чисел (Н, х, у) — выходные данные процедуры Ехтечпнп Еос~.лэ(а, и). Тогда д = 1, поскольку а Е Е„" и справедливо равенство ах+ пу = 1, или, что то же самое, ах = 1 (щооп) .
Таким образом, класс [х]„— обратный классу [а]„относительно операции умножения по модулю и. Доказательство того, что обратные элементы определяются однозначно, отложим до рассмотрения следствия 31.26. И В качестве примера вычисления мультипликативных обратных элементов рассмотрим случай а = 5 и п = 11, Процедура Ехтньлзнэ Епс1Лэ(а, п) возвращает тройку чисел (с1,х,у) = (1, — 2,1), так что 1 = 5 (-2) + 11 1. Таким образом, число -2 (т.е. 9 пюг1 11) — мультипликативное обратное по модулю 11 к числу 5. Часть Ч11.
Избранные темы 972 Далее в оставшейся части этой главы, когда речь будет идти о группах (Е„, +„) и (Е'„, „), мы будем обозначать классы эквивалентности представляющими их элементами, а операции +„и „вЂ” знаками обычных арифметических операций + и (последний знак может опускаться) соответственно. Кроме того, эквивалентность по модулю и можно интерпретировать как равенство в г.„. Например, оба выражения, приведенные ниже, обозначают одно и то же: ах = 5(тайп), [а]„ „ [х]„ = [Ь]„ . Для дальнейшего удобства иногда группа (Я, ш) будет обозначаться просто как Я, а из контекста будет понятно, какая именно операция подразумевается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
