Алгоритмы - построение и анализ (1021735), страница 197
Текст из файла (страница 197)
Избранные темы 962 31.2 Наибольший общий делитель В этом разделе описан алгоритм Евклида, предназначенный для эффективного вычисления наибольшего общего делителя двух целых чисел. Анализ времени работы этого алгоритма выявляет удивительную связь с числами Фибоначчи, которые являются наихудшими входными данными для алгоритма Евклида. Ограничимся в этом разделе неотрицательными целыми числами. Это ограничение обосновывается уравнением (31.8), согласно которому боб (а, Ь) = бсс1Оа~, )ЬО.
В принципе, величину бед (а, Ь) для положительных целых чисел а и Ь можно вычислить, пользуясь разложением чисел а и Ь на простые множители. В самом деле, если разложения чисел а и Ь имеют вид ь =р",ру'...ру, (31.11) (31.12) где нулевые показатели экспоненты используются для того, чтобы в обоих разложениях были представлены одинаковые множества простых чисел рырз,...,р„ то можно показать, что пнп(епй) ппп(е2,/з) т!п(е„,~у) В упражнении 31.2-1 предлагается показать, что это действительно так. Однако в разделе 31.9 будет показано, что время работы самых эффективных на сегодняшний день алгоритмов разложения на множители не выражается полиномиальной функцией; оии работают менее производительно.
Алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя, основан на сформулированной ниже теореме. * 31.1-10. Докажите теорему 31.8. 31.1-11. Разработайте эффективный алгоритм для операций деления )3-битового целого числа на более короткое целое число и вычисления остатка от деления )3-битового целого числа на более короткое целое число. Время работы алгоритма должно быть равно О (13з).
31.1-12. Разработайте эффективный алгоритм преобразования заданного )3-битового (двоичного) целого числа в десятичное. Докажите, что если умножение или деление целых чисел, длина которых не превышает )3, выполняется в течение времени М ()3), то преобразование из двоичной в десятичную систему счисления можно выполнить за время Е) (М (~3) )8)3). (Указание: воспользуйтесь стратегией "разделяй и властвуй", при котором верхняя и нижняя половины результата получаются в результате отдельно выполненных рекурсивных процедур.) Глава 31.
Теоретико-числовые алгоритмы 9б3 Теорема 31.9 (Рекурсивная теорема о НОД). Для любого неотрицательного целого числа а и любого положительного целого числа Ь справедливо соотношение ксс1(а,Ь) = ксс1(Ь,а пюс1 Ь). Доказаосвльслсво. Покажем, что величины бсс1(а, Ь) и ксс1(Ь,а шос1 Ь) делятся друг на друга, поэтому они должны быть равны друг другу (поскольку оба они неотрицательны) согласно уравнению (31.5). Сначала покажем, что бсс1 (а, Ь) ! ксс1 (Ь, а пюс1 Ь). Если с1 = ксс1 (а, Ь), то с( ) а и с1 ! Ь. Согласно уравнению (3.8), (а тпос1 Ь) = а — 96, где д = '1а/Ь|.
Поскольку величина (а шос1 Ь) представляет собой линейную комбинацию чисел а и Ь, то из уравнения (31.4) следует, что с( ! (а пюс1 Ь). Таким образом, поскольку с( ( Ь и с1 ! (а шос1 Ь), согласно следствию 31.3, с1 ~ бсс1 (Ь, а пюс1 Ь) или, что то же самое, бсс1 (а, Ь) ! 8сс1 (Ь, а пюс1 Ь) . (31.14) Соотношение ксс1(Ь,а шос1 Ь) ~ ксс1 (а, Ь) доказывается почти так же. Если ввести обозначение с1 = йсс1 (Ь,а шос1 Ь), то сК ! Ь и с1 ~ (а шос1 Ь). Поскольку а = 96+ (а шос1 Ь), где д = '1а/61, а представляет собой линейную комбинацию величин Ь и (а пюс1 6). Согласно уравнению (31.4), можно сделать вывод, что с1 ! а.
Поскольку с( ! 6 и с1 ! а, то, согласно следствию 31.3, справедливо соотношение с1 ! ксс1 (а, Ь) или эквивалентное ему ксс1(Ь,а пюс1 Ь) ~ ксс1(а, Ь). (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) = ах + Ьу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
