Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 18
Текст из файла (страница 18)
[ИМЗЕ'] Асимптотическая оценка времени выполнения алгоритма Е в виде уравне- ния (22) является слишком грубой для того, чтобы использовать ее для получения осмы- сленных значений чисаа А', если только оно не является очень большим, поскольку при значениях чиска Аг, с которыми обычно приходится иметь дело, величина !и!пИ всегда сравнительно мела. Выполните более тонкий анализ, позволяющий уточнить поведение уравнении (22) для приемлемых значений числа А'.
Поясните также, как выбирать зна- чение !и ш, минимизирующее (22), за исключением случаев, когда множитель достигает величины ехр(0(!об !об Ф)). 37. [МЙ7] Докажите, что квадратный корень из любого положительного целого числа (7, если толька оно не является точным квадратом, имеет периодическую цепную дробь вила мЪ = И+//оп,..,а„,2И,ам...,а„,2В,ам...,а„, Ж,...//, где гс = [~/ю] и (ап...,а„) — палиндром (т. е.
симметричная последовательность а, = а«+~-; при 1 <1< п). 38. [23] (Интересные вросшие числа.) Для 0 < 3 < 9 найдите наибольшее 50-разрядное простое число Рш которое содержит максимально возможное количество десятичных раз- рядов, равных И. (Сначала найдите максимум по З, а затем — наибольшее такое число.) 39, [ЗО] Для многих простых чисел р характерно свойство, состоящее в том, что числа 2р+ 1 также являются простыми, например б -ь 11 -+ 23 -+ 47, Обобщая, можно сказать, что число 9 — преемник чишш р, если р и 9 — оба простые числа и 9 = 2 'р+1 для некоторого ь Й > О.
Например, 2 -т 3 -+ 7 -+ 29 -+ 59 -+ 1889 -т 3779 -+ 7559 -+ 4058207223809 -т 32 465 657 790 473 -+ 4 462 046 030 502692 971 872 257 -+ 95(ЗО разрядов пропущено) 37 -+ наименьший преемник для числа 95... 37 содержит 103 цифры. Найдите максимально длинную цепочку преемников простых чисел. ь 40. [М86] (А.
Шамир (А. БЬышг),) Рассмотрим абстрактный автомат, который может в течение одного цикла выполнять операции х + у, х — у, х . у н [х/у] нал целымн числами х и у произвольной длины; длина таких чисел не имеет значения. Автомат хранит их в памяти с произвольным доступом и может выбирать для выполнения операций различные шаги программы в зависимости от того, будет ли для заданных чисел х и у выполняться равенство х = у. Назначение данного упражнения — показать, что в таком автомате можно применить изумительно быстрый способ разложения чисел на простые множители.
(Поэтому, вероятно, будет достаточно трудно показать, что на реальных компьютерах разложение на простые множители выполнить исключительно сложно, хотя мы н подозреваем, что это так.) а) Ддя заданного целого числа и > 2 найдите способ вычисления на таком гипотетическом автомате величины н! за О(Ьтбп) циклов. [Указание. 5>ли А — достаточно большое целое число, то биномнальные коэффициенты (е) = тн!/(пт — й)! М можно легко вычислить по значению числа (А+ 1) .] Ь) Покажите, квк на таком автомате вычислить число /(и) за 0(1ой н) циклов для заданного целого значения и > 2 со следующими свойствами; /(и) = и, если и — просто» число, в противном случае /(и) — собствштный делитель (необязательно простой) числа и.
[Указание. Если и эе 4, то одной из таких функций /(н) ютляется йсб(ш(и), тт), где т(п) = ш!п(ш [ т! пюг! тт = О).] (Как следствие (Ь), полное разложение на простые множители произвольно большого числа и можно найти, выполнив только 0(!обо) арифметических операций. Для заданного частичного разложения и = тц... и, каэкдое из чисел и;, не являющихся пртктыми, можно заменить функциями /(и;) (ит//(пт)) за Я О(!ой и;) =О(!обо) циклов. Этот процесс можно повторить до тех пор, пока все числа тц не станут простыми.) ь 41.
[Мйу] (Лагариас (Ьайщбаэ), Миллер (Мшег) н Одлыжко (От!!ух)то).) Назначение этого упражнения — показать, что может быть вычислено количество простых чисел„меньших Ат~, если принимать во внимание только простые числа, меньшие !т", и, таким образом, вычислять величину я(Ат ) за 0(Фэ+") шагов. Положительное целое число, для которого все простые множители превышают число тн, назовем т-долгожителем; так что один т-долгожитель останется в решете Эратосфена (упр.
8) после просеивания всех чисел, кратных простым числам, не превышающим пт. Пусть /(х, пт) — количество тл-долгожителей, которое не превышает х, и пусть /ь(х, тл)— количество таких долгожителей; для которых имеется ровно х простьсх множителей (учитывая кратность). а) Докажите, что х(Ат ) = х(!т') + /(Атз, Ат) — 1 — /т(Ат~, !тт). Ь) Поясните, как вычислить /з(Ю~, Ат) по значениям э(х) для х < ттт~. Используйте метод вычисления значения /з(1000, 10) вручную. с) Та же задача, что и в (Ь), но вместо /т(тт'з, Ат) вычислите /т()т1, Ат).
[Указание. Используйте толтдество /(х,рт) = /(х,рт т) — /(х/р,,р;-т), где рт есть 2-е простое и ре = 1.] 6) Проатталтгзируйте структуры данных, необходимые для эффективного вычисления величин при решении задач (Ь) и (с). 42. [Муб] (Х. В. Лежтра (мл.) (Н. Ъ!т. Ьевяэга, Зг).) Для заданного интервала 0 < т < е < Ат, в котором г .1 э и Ат .1 а, покажите, что можно найти все делители числа Ат, равные и г (по модулю з), выполнив 0([)й/зз]ыз!обз) хорошо подобранные арифметические операции иад ()б У)-битовыми числами. [Указание. Примените результаты упр.
4.5.3-49.] ь 43. [М4Я] Пусть т = р4 — г-битовое целое число Блюма, как в теореме 5,5Р, и пусть Ф = (у [ у = х~ люб т для некоторого х). Тогда Ц имеет (р+ 1)(у+ 1)/4 элементов и каждый из этих элементов у б ю,„имеет единственный квадратный корень х = ~/у, такой, что х б !з . Предположим, что С(у) — это алгоритм, который правильно предсказывает значение ./у люб 2 с вероятностью > -' + е, где у — случайный элемент См.
Паза этого упражиеиия — доказать, чтю задача, решаемая при помощи С, почти так же трудна, как и задача разложения на простые множители числа т, а) Разработайте алгоритм А(С,т, е,у, Ю), который использует случайные числа, и алгоритм С для тоге, чтобы предсказать без обязательного вычисления ./у, будет ли данное целое число у принадлежать б),. Результат выполнения алгоритма должен быть корректным с вероятностью > 1 — 5, а время Т(А) его выполнения не должно превышать величины 0(е ~(!обб ')Т(С)) в предположении, что Т(С! > г . (Если Т(С) < гз, в втой формуле замените Т(С) величиной (Т(С) + гз),) Ь) Разработайте алгоритм Р(С, т, с), который находит множители числа т и ожидаемое время выполнения которого равно Т(Р) = 0(г~(г з + е ~(!обе 1)Т(С))). Указание.
Для 0 < в < т и фиксированного у б СЗ~, положим гв = в~/ушобт и Лв = ге пес!2. Учтем, чтю Л(-в) + Лв = 1 и Л(в1 + + и„) = (Лв~ + + Лив + [(ге~+ .+ги,„)/т]) шо42. Имеем далее г(~в) = 1(ги+ тЛи); здесь величина $и заменяет (шЭЛи) шобт. Если хв б Я,ь, имеем г(хи) = визу, поэтому алгоритм С обеспечивает способ предсказания величины Л» для примерно половины всех в.
44. [М85] (Й. Хвастал (1. НЬзгаб).) Покажите, что нетрудно найти х в случае, когда а;р+ апх+ашхз+а;зхз ш 0 (по модулю т;), 0 < х < ти бсб(а1е,ал, аш, а,з,1л;) = 1 и т, > 10 при 1 < 1< 7, если т; Л глз при 1 < ! < у < 7. (Все переменные — целые числа, и все оии, кроме х, известны.) Указаиое. Когда Ь вЂ” произвольная иеособая матрица вещественных элементов, алгоритм Ленстра (1елзсга) и Ловача (Ьюийш) [Магйешзз!жйе Алла!ел 201 (1982), 515-534] эффективно находит ненулевой целочисленный вектор в = (им,в„), такой, что длина (из') < ~/ц2в ]бес,б[ы". ' 45.
[М41] (Дж, М. Поллард (1. М, Ро!!агб) и Клаус-Петер Шпорр (С1алз-Регег ЯсЬпоп).) Покажите„что для целых чисел х и у, заданных целых чисел а, Ь и и, для которых а6 Л и и и нечетко, существует эффективный способ решения уравнеиия х — ау ш 6 (по модулю л) 3 2 даже в том случае, когда неизвестно разложение иа простые множители числа и. [Указаиие.
Используйте тождество (хз — ау~э)(хзз — аузз) = хз — ауз, где х = х1хз — ау~уз и у = хЮз + хзу1 ] 40. [ггМЯО] (Л, Эдлеман (Ь. Аб!ешаз).) Пусть р — достаточно большое простое чигло и а — простой корень по модулю р; таким образом, все целые числа Ь в интервале 1 < Ь < р могут быть записаны в виде Ь = а шоб р для некоторого единствеиного числа л из интервала 1 < и < р. Используя идеи, аизлогичиме идеям из алгоритма Диксона разложения иа простые множители, разработайте алгоритм, который почти всегда по ззданиому Ь находит число и за О(р') шагов для всех е > О.
[Указаиис. Начните с формирования набора чисел л„таких, что числю агч шоб р имеет только малые простые множители.] 42. )мбб) некоторая цитата из литературного источника в = втвз, представлешая в АОСН-кодах, в звтоифрованном виде выглядит как (лтз шот) Ат, вз зшоб Аг) = ~14еэтетьсьз1о92ьз1ве9сое1в4е444зо4312со14ь2эс2ииш07ьвомзт1сзскозотОзеетс4озе1з2424139 еьтзтте2еььоосз1Отз2т4т4вэ63осщнз371мвтэло1з26втлэвзтлзз3овззт46з1ь7взО7вьо17т2ьтьиз, 1$902$326ЕЕ09$19$42$901940763772ВЗЕ333007941ЕЭВИ192$9136В.'РСВВВБВЕ431719304772799333730 В20$1341ВОЕВЭВЕЭСзмЭВ$03309$3 17 3$7639С74 Ы1261В34С32646713490СОС28$7 $$24$4$3шоозьовьС7) в шестнадцатеричных обозначениях, где Ат равно 1 7В23$ЗВ9$Э$ЕС1697Е760В40160С4Ов42Э6О12$ь97Е4ЭО11ь72ЭаЗ3т6зтВЭо$2247С4ьь6791О4СЕО2ВС$9 И 9$1761 ьтиостетеьььзоияиззьсшамш013392$717433303$92$тотзввеезызтлзттоьвтзьвзаииоеоз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
