Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 215
Текст из файла (страница 215)
Доказальельсшво. Докажем лемму путем индукции по !с. В качестве базиса индукции примем lс = 1. Тогда Ь > 1 = Рз и, посюльку а > Ь, автоматически выполняется соотношение а > 2 = Рз. Поскольку Ь > (а шос) 6), при каждом рекурсивном вызове первый аргумент строго больше второго; таким образом, предположение а > 6 выполняется при каждом рекурсивном вызове. Глава ЗЕ Гворвтиво-числовые алгоритмы Примем в качестве гипотезы индукции, что лемма справедлива, если произведено Й вЂ” 1 рекурсивных вызовов; затем докажем, что она выполняется, если произведено гс рекурсивных вызовов. Поскольку гс > О, то и Ь > О, и в процедуре Епсьпз(а, Ь) рекурсивно вызывается процедура Епсь1п(Ь, а шоб Ь), в которой, в свою очередь, делается Ь вЂ” 1 рекурсивных вызовов.
Далее, согласно гипотезе индукции выполняются неравенства Ь > Р~+з (что доказывает часть леммы) и (а пюс1 Ь) > 6». Мы имеем Ь + (а пюс1 Ь) = Ь + (а — Ь | а/6! ) <а, поскольку из а > Ь > О следует 1а/6) > 1. Таким образом, а > Ь + (а шос1 Ь) > р»+з + Р'» о».~-2 . Из этой леммы непосредственно следует сформулированная ниже теорема.
Теорема 31.11 (Теорема Ламе (Танге)) Если для произвольного целого числа Ь > 1 выполняются условия а > 6 > 1 и 6 < Г»+ы то в вызове процедуры Епсшп(а, 6) производится менее )с рекурсивных вызовов. Можно показать, что верхняя граница теоремы 31.11 является лучшей из возможных, показав, что вызов ЕОсшп(Г»+ы Р») выполняет ровно й — 1 рекурсивных вызовов при )с > 2. Воспользуемся индукцией по й. В базисном случае Ь = 2, и вызов епсь1п(Ьз, ез) делает Ровно один РекУРсивный вызов епсьпз(1, О). (мы начинаем с )с = 2, поскольку при Ь = 1 не выполняется неравенство Гз > Рп) В качестве шага индукции примем, что ЕОСЬ1П(Ь», Е» з) выполняет ровно й — 2 рекурсивных вызова. При )с > 2 мы имеем Р» > Р~ з > О и 6».»~ = 6» + Г» з, и согласно упр.
31.1.1 Р~~.~ пюс1 Г» = Р» з. Таким образом, бес)(6»+ы 6») = ясс)(Ры Р~+~ шос( Р~) = бес)(Г» г»-~) Следовательно, в процедуре Епсып(Р~+ы Г») рекурсия осуществляется на один раз больше, чем в процедуре Епсь1п(с», Г» з), или ровно )с — 1 раз, что совпадает с верхней границей теоремы 31.11. Поскольку число Г» приблизительно равно ф»/т/5, где ф — золотое сечение (1+ чгб)/2, определенное уравнением (3.24), количество рекурсивных вызовов в процедуре Епсшп равно 0(1яЬ).
(Более точная оценка предлагается в упр. 31.2.5.) Отсюда следует, что если с помощью алгоритма Епсшп обрабатывается два )3-битовых числа, то в нем выполняется 0()3) арифметических операций и 0(ф) битовых операций (в предположении, что при умножении и де- 980 Часть 171 Иэбраляые темы ленин )3-битовых чисел выполняется 0()3з) битовых операций). Справедливость этой оценки предлагается показать в задаче 31.2. Развернутаи форма алгоритма Евклида Теперь перепишем алгоритм Евклида так, чтобы с его помощью можно было извлекать дополнительную полезную информацию„в частности, чтобы можно было вычислять целые коэффициенты х и у, такие, что 11 = 8сс1(а, Ь) = ах + Ьу .
(31.16) Заметим, что числа х и у могут быть равными нулю или отрицательными. Эти коэффициенты окажутся полезными позже при вычислении модульных мультипликативных обратных значений. В качестве входных данных процедуры Ехтп)ч080- ЕОСи0 выступает пара неотрицательных целых чисел, а на выходе эта процедура возвращает тройку чисел (Н, х, у), удовлетворяющих уравнению (31.16). Ехте)чоеп-ЕОсь10 (а, Ь) 1 !ТЬ ==О 2 гетцгн (а, 1, О) 3 е!ве (д',х',у') = ЕхтВ14080-ЕОси0(Ь,а шос) Ь) 4 (8, ',у) = И',у', ' — ~а/61 у') 5 гегнгп (з(, х, у) На рис. 31.1 проиллюстрировано вычисление 8с11(99, 78) процедурой Ехтйм080- ЕОСь10.
Процедура ЕХТВЫ080-ЕиСЫ0 представляет собой разновидность процедуры Епсып. Строка 1 в ней эквивалентна проверке "Ь == О" в строке 1 процедуры Еисып. Если Ь = О, то процедура Ехт81ч080-Еисып в строке 2 возвращает не только значение И = а, но и коэффициенты х = 1 и у = О, так что а = ах + (п). Если Ь Ф О, то процедура Ехт81ч080-Епсп0 сначала вычисляет набор величин а Ь (а/Ь) з( х у Рнс. 31.1. Вычисление ксб(99,78) процедурой Ехтпмоко-Восыо.
В кахщой строке показан один уровень рекурсии: значения входных данных о н Ь, вычисленное значение (о/Ь) н возвращаемые значения 4, я н у. Возвращаемая тройка (Ы, я, у) становится тройкой (о', х', р'), используемой на следующем более высоком уровне рекурсии. Вызов Ехтпмово-Еосыо(99, 78) возвращает (3, — 11, 14), так что ясб(99, 78) = 3 = 99 (-11) + 78 .
14. 99 78 1 78 21 3 21 15 1 15 6 2 6 3 2 3 О 3 -11 14 3 3 — 11 3 — 2 3 3 1 — 2 3 О 1 3 1 О Глава 36 Теоретико-числовые алгоритмы 9о! (с(', х', у'), таких, что а' = 8сс((Ь, а пюс( Ь) и аг = Ьх~ + (а пюс( Ь)у . (31.17) Как и в процедуре Енссцэ, в этом случае мы имеем Н = 8сс((а, 6) = д' = йсс)(Ь,а пюс( 6). Чтобы получить значения х и у, для которых выполняется равенство с( = ах + Ьу, сначала перепишем уравнение (31.17) с использованием равенств с( = с(' и (3.8): с( = Ьх' + (а — 6 1а/63)у' = ау + Ь(х — (а/6) у~) .
Таким образом, выбор х = у' и у = х' — 1а/63 у' удовлетворяет уравнению с( = ах + 6у, что доказывает корректность процедуры ЕХТВНРЕ1З-ЕОСЫП. Поскольку количество рекурсивных вызовов в процедуре Есс~.1п равно количеству рекурсивных вызовов в процедуре ЕХТВНПЕР-ЕБСШП, время работы процедуры ЕОСЬ1П с точностью до постоянного множителя равно времени работы процедуры Ехтнн1зегз-ЕОсп1э. Другими словами, при а > 6 > О количество рекурсивных вызовов равно 0(186).
Упражнения 31.2.1 Докажите, что из уравнений (31.11) и (31.12) вытекает уравнение (31.13). 31.2.2 Вычислите значения (а, х, у), возвращаемые при вызове процедуры ЕХТЕНПВПЕысшп(899,493). 31.2.3 Докажите, что для всех целых чисел а, /с и и справедливо соотношение 8сс((а,п) = йсй(а+ lсп, и) . 31.2.4 Перепишите алгоритм ЕОСЬ11з в итеративном виде, с использованием памяти фиксированного объема (т.е.
в ней должно храниться не более некоторого фиксированного количества целочисленных значений). 31.2.5 Покажите, что если а > Ь > О, то вызов Енсшп(а, Ь) делает не более 1 +!ока Ь РекУРсивных вызовов. УлУчшите этУ оценкУ до 1 + 1ойа(6/ йсг((а, 6)). 31.2.6 Что возвращает вызов Ехтвн1злп-Ессшп(Рь+ы Ьь)? Докажите верность своего ответа. 9бг Часть е11, Избранные тены зз.г.т Определим функцию ясб для более чем двух аргументов с помощью рекурсивного уравнения ясд(ао,ам..., а„) = ясб(ао, ясб(аз, аг,..., ен)). Покажите, что значение этой функции ие зависит от порядка ее аргументов. Покажите также, как найти целые числа хо,хы...,х„, такие, что ясб(ао,аь...,он) = сохо + азх1+ + а„х„.
Покажите, что количество операций деления, выполняемых алгоритмом, равно 0(п + 1я(шах (ао, аь, .., а„))). Зз.г.а Определим иаимеиьпеее одеиее кратное (1еаз~ сопипоп пш!йр1е) и целых чисел аы аг,..., а„, обозначаемое!сш(аь аг,..., ан), как наименьшее неотрицательное целое число, кратное каждому из аргументов ео Покажите, как зффективио вычислить величину 1сш(аь аг,..., а„), используя в качестве подпрограммы (двух- аргументную) операцию ясг). зз.г.р Докажите, что числа пь пг, пз и пя попарно взаимно простые тогда и только тогда, когда кс6(пгпг,пзп4) = кос)(пзпз,пгп4) = 1 .
Покажите, что справедливо более общее утверждение, согласно югорому числа пь пг,..., пь попарно взаимно просты тогда и только тогда, когда ~1й к1 пар чисел, образованных из пь являются взаимно простыми. 31З. Модульная арнфметнка Неформально модульную арифметику можно считать обычной арифметикой, вычисления в которой выполняются иад целыми числами, за исключением того, что если мы работаем по модулю числа и, то любой результат х заменяется элемеитом множества (О, 1,..., и — 1), равным числу х по модулю п (т.е.
х замеияется величиной х шод и). Описанной выше неформальной модели достаточно, если ограничиться операциями сложеиия, вычитания и умножения. Более формализоваииая модель модульной арифметики, которая будет представлена ниже, лучше всего описывается в рамках теории групп. Конечные группы Группа (ягоир) (Я, Ю) представляет собой множество Я, иа котором определена бинарная операция Ю, обладающая перечисленными ниже свойствами. 1. Замкнутость: для всех а, Ь Е Я справедливо а ЮЬ Е Я. 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
