Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 214
Текст из файла (страница 214)
— Примеч. иер. (31.6) (31.7) (31.8) (31.9) (31.10) 973 Глава 31, Теортиико-числовые ивгоритыы поэтому величина а шов) в также является линейной комбинацией чисел а и 6. Но посюльку О < а шов) в < в, выполняется соотношение а шов) в = О, так как ив наименьшая положительная из таких линейных комбинаций. Поэтому в ~ а; аналогично можно доказать, что в ~ Ь, Таким образом, в является общим делителем чисел а и 6, поэтому справедливо неравенство 8сг((а, Ь) > в.
Из уравнения (31.4) следует, что 8сг((а, Ь) ~ в, поскольку величина 8сг)(а, Ь) делит и а, и Ь, а в представляет собой линейную комбинацию этих чисел. Но из того, что бсг1(а,6) ~ в и в > О, следует соотношение 8сг)(а, 6) < в. Совместное применение неравенств 8сг)(а, 6) > в и 8сг)(а, 6) < в доказывает справедливость равенства 8се((а, 6) = в; следовательно, можно сделать вывод, что в — наибольший общий делитель чисел а и Ь. Слвдсогвие 31.
3 Для любых целых чисел а и Ь из соотношений д ) а и е( ! Ь следует г( ) 8сг)(а, Ь). Доквзвшечьсшво. Это следствие является результатом уравнения (31.4), посюльку согласно теореме 31.2 величина 8сг)(а, Ь) является линейной комбинацией чисел а и 6. Слвдсигвие 31. 4 Для любых целых чисел а и Ь и произвольного неотрицательного целою числа п справедливо соотношение 8св((ап, Ьп) = пйсв)(а, 6) . Доказательство. Если п = О, доказательство тривиально. Если п > О, то 8сг)(ап,Ьп) является наименьшим положительным элементом множества (апх + 6пу: х, у е У,), в п раз превышающим наименьший положительный элемент множества (ах+ (и1: х,у Е е').
Слвдсшвие 31. 5 Для всех положительных целых чисел п, а и 6 из п ~ аЬ и 8сс1(а, п) = 1 следует, что п ! Ь. Доквзагивльсгиво. Доказательство этого следствия читателю предлагается выполнить самостоятельно в упр. 31.1.5. Взаимно простые целые числа Два целых числа а и Ь называются взаимно красивыми (ге1абие1у рпше), если единственный их общий делитель равен 1, т.е. если бсср(а, Ь) = 1. Например, числа 8 и 15 взаимно простые, посюльку делители числа 8 равны 1, 2, 4 и 8, а делители числа 15 — 1, 3, 5 и 15.
В сформулированной ниже теореме утверждается, что если два целых числа взаимно простые с целым числом р, то их произведение также является взаимно простым с числом р. 974 Часть Иб Избранные тены Теорема 31. 6 Для любых целых чисел а, 6 и р из ясс)(а,р) = 1 и кос)(Ь,р) = 1 следует ясз((аЬ,р) = 1. Доквзительствзь Из теоремы 31.2 следует, что существуют такие целые числа х, у, х' и у', для которых ах+ ру = 1, Ьх' + ру' = 1 . Перемножив эти уравнения и перегруппировав слагаемые, получаем аЬ(хх') + р(уЬх'+ у'ах + руу') = 1 .
Поскольку положительная линейная комбинация чисел аЬ и р равна 1, примене- ние теоремы 31.2 завершает доказательство. Говорят, что целые числа пы па,..., пь локарно взаимно нростме (рапзн1зе ге!айте!у рпше), если при з ф 3' выполняется соотношение йсз)(п;, п ) = 1. Единственность разложении на множители Элементарный, но важный факт, касающийся делимости на простые числа, сформулирован в приведенной ниже теореме. Теорема 31. 7 Для любого простого числа р и всех целых чисел а и Ь из условия р ( а6 следуют либо соотношение р ~ а, либо соотношение р ~ Ь, либо они оба.
Доказательство. Проведем доказательство методом от противного. Предположим, что р ! аЬ, но р 1 а и р 1 6. Таким образом, ясс)(а,р) = 1 и ясз)(Ь,р) = 1, поскольку единственными делителями числа р являются 1 и р и согласно предположению на р не делится ни а, ни 6.
Тогда из теоремы 31.6 следует, что ясй(аЬ, р) = 1, а это противоречит условию, что р ~ а6, поскольку из него следует, что коз)(аЬ, р) = р. Это противоречие и завершает доказательство теоремы. ° Из теоремы 31.7 следует, что любое целое число можно единственным образом представить в виде произведения простых чисел.
Теорема 31.8 (Единственность разложения ни множители) Имеется единственный способ представления составного числа а в виде произведения где р, — простые числа, р1 < рз « р„, а е, — положительные целые числа. Доказательство. Доказательство этой теоремы оставляется читателю в качестве упр.
31.1.11. Глоео 36 Теоретико-числовые олгоритиы В качестве примера число 6000 можно разложить на простые числа следующим единственным образом: 24 3 ° бз. Упражнения 31.1.1 Докажите„что если а > Ь > 0 и с = а + Ь, то с пюс) а = Ь. 31.1.г Докажите, что простых чисел бесконечно много. (Указание: покажите, что ни одно из простых чисел рм рз,..., рь не является делителем числа (рзрз рь) + 1,) 31.1.3 Докажите, что если а ! Ь и Ь | с, то а ( с.
31.1.4 Докажите, что если р простое и 0 < lс < р, то бес)(/с, р) = 1. 31.1.5 Докажите следствие 31.5. 31.1.6 Докажите, что если р простое и 0 < )с < р, то р ~ ("„). Сделайте вывод о том, что для всех целых чисел а и 6 и всех простых р (а + 6)Р ка аР + 6Р (пюс) р) . 31.1. 7 Докажите, что если а и 6 являются произвольными положительными целыми числами, такими, что а ~ Ь, то (х гаос) 6) гпос) а = х пюд а для любого х. Докажите, что при тех же исходных предположениях из х т у (гаос) 6) следует х = — у (пюд а) для любых целых чисел х и у.
31.1.8 Говорят, что для всех целых 6 > 0 целое число п представляет собой )с-ю степень (Кцз рожег), если существует целое число а, такое, что а = и. Кроме того, число и > 1 является нетривиальной стененьт (полито)а1 рожег), если оно является )с-й степенью для некоторого целого lс > 1.
Покажите, как определить, является ли заданное )3-битовое целое число и нетривиальной степенью, за время, выражаемое полиномиальной функцией от ~3. 97б Часть Р77 Избранные темы 31.1.9 Докажите уравнения (31.бН31.10). 31.1.10 Покажите, что оператор 8сц ассоциативен, т.е. докажите, что для всех целых чисел а, 6 и с йсс((а, 8сс1(6, с)) = йсс)(8с~Ца, Ь), с) . 31.1.11 * Докажите теорему 31.8. 31.1.12 Разработайте эффективный алгоритм для операций деления,З-битового целого числа на более короткое целое число и для вычисления остатка от деления ~3- битового целого числа на более короткое целое число.
Алгоритм должен выполняться за время ез()3з). 31.1. 13 Разработайте эффективный алгоритм преобразования заданного 13-битового (двоичного) целого числа в десятичное. Докажите, что если умножение или деление целых чисел, длина которых не превышает 3, выполняется за время М(13), то преобразование из двоичной в десятичную систему счисления можно выполнить за время ез(М(~3) 18 13). (Указаниес воспользуйтесь стратегией "разделяй и властвуй", при которой верхняя и нижняя половины результата получаются путем отдельного выполнения рекурсивных процедур.) 31.2. Наибольший общий делитель В этом разделе рассматривается ашоритм Евклида, предназначенный для эффективного вычисления наибольшего общего делителя двух целых чисел. Анализ времени работы этого алгоритма выявляет удивительную связь с числами Фибоначчи, которые являются наихудшими входными данными для этого алгоритма.
Ограничимся в этом разделе только неотрицательными целыми числами. Это ограничение обосновывается уравнением (31.8), которое гласит, что 8сс)(а,Ь) = йсг)(!а/, /Ь!). В принципе, можно вычислить йсс)(а, Ь) для положительных целых чисел а и 6, пользуясь их разложением на простые множители. Действительно, если (31.11) (31.12) где нулевые показатели экспоненты используются для того, чтобы в обоих разложениях были представлены одинаковые множества простых чисел ры рз,...,р„ Глаеа 16 Теоретико-числовые алгоритмы 977 то можно показать (см.
упр. 31.2.1), что лг кч ппп(еыЛ) пип(ел,Ы пип(е„1,) (31.13) Однако в разделе 31.9 будет показано, что время работы самых эффективных на сегодняшний день алгоритмов разложения на множители не выражается полиномиальной функцией; они работают менее производительно. Таким образом, непохоже, чтобы этот подход к вычислению наибольшего общего делителя привел к эффективному алгоритму. Алгоритм Евклида, предназначенный для вычисления наибольшего общего делителя, основан на сформулированной ниже теореме. Теорема 31.
9 (Рекурсивная теорема о иаибольшем обатам делителе) Для любого неотрицательного целого числа а и любого положительного целого числа 6 справедливо соотношение йсг((а, Ь) = 8сг1(Ь, а пюс1 Ь) . Доказательство. Покажем, что величины 8се)(а, Ь) и 8се)(6, а шос) Ь) делятся одна на другую, а поэтому согласно (31.5) они должны быть равны одна другой (посюльку обе они неотрицательны). Сначала покажем, что бсс1(а, Ь) ! 8сг)(6, а пюс1 6). Если положить с( = йсс1(а, Ь), то с( ( а и Ы ! Ь. Согласно (3.8) а пюс1 Ь = а — дЬ, где 9 = '(а/6) . Поскольку а шос1 Ь оказывается линейной юмбинацией а и 6, из уравнения (31.4) вытекает, что б ~ (а пюс1 Ь). Таким образом, поскольку с( ( Ь и с( ( (а шос( Ь), из следствия 31.3 вытекает, что б ( 8сс((Ь, а пюс1 6) или, что эквивалентно, что 8сг)(а, Ь) ) 8сс((6, а пюс1 Ь).
(31. 14) Соотношение 8сс)(Ь, а шос) 6) / 8сс((а, Ь) доказывается почти так же. Если мы теперь положим с( = 8сс((Ь,а гпос1 Ь), то г1 / Ь и г( ! (а шоб 6). Поскольку а = 96+ (а шос( 6), где д = (а/Ь|, получается, что а является линейной комбинацией Ь и (а пюс1 Ь). Согласно (31.4) заключаем, что с( / а. Поскольку б ! Ь и с( ! а, согласно следствию 31.3 справедливо с( / 8сг)(а, Ь) или, что эквивалентно, 8сг((Ь, а гас<1 Ь) / 8сг((а, Ь).
(31.15) Использование уравнения (31.5) в комбинации с уравнениями (31.14) и (31.15) завершает доказательство. Алгоритм Евклида В книге Евклида "Начала" (ок. 300 г. до н.э.) описывается приведенный ниже алгоритм вычисления 8сс( (хотя на самом деле он может иметь и более раннее происхождение). Алгоритм Евклида выражается в виде рекурсивной программы и основан непосредственно на теореме 31.9.
В качестве входных данных в нем выступают произвольные неотрицательные целые числа а и 6. Часть 971 Избранные тены 97В Ессснэ(а, Ь) 1!6==О 2 гегцгп а 3 е1зе гегпгп Еисшп(Ь, а шог! 6) В качестве примера работы процедуры Епсшп рассмотрим вычисление величи- ны ясг)(30, 21): Епсшп(30, 21) = Ессшп(21, 9) = Ессс!гэ(9, 3) = Еисшп(3, 0) =3. В приведенных выше выкладках мы видим три рекурсивных вызова процедуры Еусс!гэ. Корректность процедуры Евсин следует из теоремы 31.9, а также из того факта, что если алгоритм в строке 2 возвращает значение а, то Ь = О, так что из (31.9) следует, что ясд(а, Ь) = ясс1(а, 0) = а.
Работа этого рекурсивного алгоритма не может продолжаться до бесконечности, посюльку второй аргумент процедуры всегда строго убывает при каждом рекурсивном вызове, и он всегда неотрицательный. Таким образом, алгоритм Еисшп всегда завершается и дает правильный ответ. Время работы алгоритма Евклида Проанализируем наихудшее время работы алгоритма Е!!сын как функцию размера входных данных а и Ь.
Без потери общности предположим, что а > 6 > О. Это предположение легко обосновать, если заметить, что если 6 > а > О, то в процедуре Еисьпэ(а, Ь) сразу же выполняется рекурсивный вызов процедуры Еисшп(Ь, а). Другими словами, если первый аргумент меньше второго, то алгоритм Еисшп затрачивает один дополнительный вызов на перестановку аргументов и продолжает свою работу.
Аналогично, если 6 = а > О, то процедура завершается после одного рекурсивного вызова, поскольку а шод 6 = О. Полное время работы алгоритма Еисс!и пропорционально количеству выполняемых им рекурсивных вызовов. В нашем анализе используются числа Фибоначчи Гы определяемые рекуррентным соотношением (3.22). Лемма 31.10 Если а > д > 1 и в результате вызова процедуры Епссцэ(а, Ь) выполняется 6 > 1 рекурсивных вызовов, то а > Гь+з и Ь > гь+!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
