Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 87
Текст из файла (страница 87)
Решение 1. Если и м р",... р',". зто число в каждом случае равно (2е~ + 1)... (2е + 1). Решение 2. Если положить и = боЦИ,п) и е = п~/1сш(д,п) для каждого делителя 4 числа вт, то можно получить взаимно однозначное соответствие. ]Е. Сезйго, Аллаб 6( Часеша11са Рига ед Арр)(сага (2) 18 (1885), 235-250, 912.] 4. См.
упр. 3,2.1.2-15(а). 5. Вудем выполнять сдвиг вправо чисел и и е до тех пор, пока ие получим, что ни одно нз них пе кратно 3. Запоминаем соответствующее значение степени 3, которое появится в наибольшем общем делителе. Затем на каждой итерации присваиваем г е- в+ в или 1 е- и — е (в зависимости от того, какая из зтях величин кратна 3), сдвигаем 1 вправо до тех пор, пока оно не перестанет быть кратным 3, после чего заменяем шах(и, е) полученным результатом. в расчет небольшие полравкн, тогда среднее в действительности будет равно л ~~ ~~ э 1 4 7.
Если чнсла и и е не являются оба четными, то равновероятен каждый из случаев (четное, нечетное), (нечетное, четное), (нечетное, нечетное) и прн этом имеем соответственно В = 1, О, О. Следовательно, в среднем В = -'. Если уж быть совсем точным, то, когда 1 < и,е < 2л, необходимо внести небольшую поправку: вероятность того, что В = 1, в действительности будет равна л 3 3 как следует из упр.
б. 6. Обозначим через Г число шагов вычитания, в которых и > е. Тогда Е = Р+ В. Если заменить исходные данные (в, е) нв (е, к), то значение С не изменится, а число г' станет равным С 1 — Р. Следовательно, Еь е = э(Сьм 1) + Ваш 1 9. В первый рвз бинарный алгоритм попадает на шаг Вб при значениях и = 1963, е = 1359; тогда 1+- 604, 302, 151 и т. д.
Нанбоэьший общий делитель равен 302. Применяя алгоритм Х, находим, что 2. 31408 — 23 2718 = 302. 10. (а) Два целых числа взаимно просты тогда и только тогда, когда оба они не делятся одновременно нн иа одно простое число. (Ь) Перегруппируем сумму в (а), принимая знаменатели равными й = р~...р,.
(Каждая из сумм в (а) я (Ь) на самом деле конечна.) (с) Так Яак (и/й) — [и/к)~ = О(п/й), то д — 2 „" Д(к)(н/и) = 2'э, 0(п/й) = О(пН ). Далее, 2 „„(и/й)т = 0(п). (6) Ящ„,и(д) м бы. [Фактически имеет место более общий, чем в (Ь), результат где суммирование в правой части берется по простым делителям и, и эта сумма равна п'(1 — 1/р',)...(1 — 1/р'„), если и ж р" ,...р', [ Замечание. По аналогии найдем множество целмх чисел й, которое с вероятностью 1/С(к) = 1/(Я„Э, 1/Н~) яВЛяЕтея МипжветВОМ, СОСтсящНМ НЗ ПрОСтЫХ ЧИСЕЛ.
ЭтО доказательство теоремы П предложено Ф. Мертенсом (Р. Мегсепз, Сгейе 77 (1874), 289- 29Ц. Такая методика дает гораздо более строгий результат, а именно: для произвольных / и д бя эпап+ 0(п!обпа) пары целых чисел и б [/(т) ../(т) + ш), е б [д(п) ., д(п) +и) являются взаимно простыми при т < и. 11. (а) Искомая вероятность равна 6/кэ, умноженному на 1+ -'+ -', т.
е. 49/(бяэ) .82746. (Ь) Среднее значение равно 6/кэ, умноженному на 1/1+ 2/4+3/9+ ., т. е. со. (Это верно, несмотря на результаты упр. 12 и 14.) 12. [Аппаб сб Мак (2) 13 (1885), 235-250, 33.) Пусть п(п) — количество положительных делителей числа и. Тогда ответ будет таким: [Следовательно, «редиее значение меныие 2, хотя в случае, когда и н в не являются взаимно простыми, онн имеют по меньшей мере два общих делителя.) 18' 1+ э + ю+''' 1+ 3+ е+'' е(1+ а + е+''') 14. (а) Е = (6/яз) 2 „,а ~(п4 = -б'(2)/б(2) = 2 „,,()пр)/(2» — !) 0.56996.
(Ь) (8/х ) 2 с>,(бнечетное)4 з)пб = /, — -')п2 ж 033891. 15. с~ = хо/из, оз = щи/из (знак зависит оттого, четно нлк нечетно число итерашхй). Это следует пз того факта, что чксла сл и оз взаимно просты (иа протяжении всего процесса выполнения алгоритма) и с1и = -сзс. (Следовательно, в момент завершения выполнения алгоритма щи = !сш(и,о), но такой мезод — не лучший путь вычисления наименьшего общего кратного. Обобщение этого метода рассмотрено в упр. 4.6.1-18.] Более подробно с данным вопросом можно ознакомиться, рассмотрев упр.
4.5.3-48. 16. В результате применения к числам с и щ алгоритма Х вычисляем такие значенпя х, при которых хс ш 1 (по модулю ял). (Это можно сделать путем упрощения алгоритма Х за счет отказа от вычисления из, сз н Сз, поскольку данные величины в ответе ие присутствуют.) Затем присвоим»о»- ихщоз)т. (Отсюда следует, как в упр. 4,5.3-45, что для реализации этого процесса при его применении к большим и-битовым числам необходимо затратить О(пз) единиц времени.
В упр. 17 и 39 рассмотрены алгоритмы, альтернативные алгоритму Х.) 12. По аналогии с методом Ньютона можно положить, что и' = (2и — сиз)шос(2»» (см, окончание раздела 4.З.Ц. Точно так же при ис щ 1+ 2'зс (по модулю 2»') ползшем и' = 1 + 2'((-ило) шоб 2'). 18. Пусть в дополнение к числам и и с числа им из, из, сп сз, сз — переменныс с многократной точностью. Расширенный алгоритм будет выполнять над числамн из и сз тс же опсрацяи, что и алгоритм В пад числаллн и н и, Новыми операциями многократной точности бУдУт; пРисвосние на шаге 14 С»- .4и„!»- ! + Всю зс с- Си» зс»- иу+ 1?оз, ил»- 1, сз»- и для всех,у. Кроме того, если на этом шаге В = О, выполняем присвоение с»- из — усы иу»- ь;, с~ »- ! для всех у и для д = (из/сз), прп малых значениях сз подобным образом модифицируется н шаг ! 1.
Внутренний цикл (шаги Ь2 и 1,3) остается неизменным. 19. (а) Пусть зз = з+ 2у+ 3». Тогда Ззз + у+ 2» = 1, 51~ — Зу — 20» = 3. Исключим у, и тогда !4 — 14» = 6. Решений нет. (Ь) На этот раз 14сз — 14» = О. Выполняем деление иа 14 и исключаем зл; общее решение имеет вид х = 8» — 2, у = 1 — 5» (» выбирается произвольно), 20. Предположим, что т > и. При гл > и = О получиы (т — с, 0) с вероятностью 2 ', а прн 1 < З < гл получим (О, 0) с вероятностью 2' . уа!ща о!» при и > 0 можно получить следующие значения, Случай 1, т = и. Из (п,п) прн 2 < ! < и переходим в (и — йп) с вероятностью !/2 — 5/2~+~ + 3/2м. (Этими значениями будут л5, 84, 1З»У5, ....) Вероятность попадания в интервал (О, и) равна и/2" ' — 1/2" з + 1/2»" з.
Вероятность попадания а интервал (я, (с) такая же, как и вероятность попадания в интервал (!с, и). Вероятность прекращения выполнения алгоритма равна 1/2" Случая Я, щ = и+ 1. Из интервала (и + 1, и) в интервал (и, и) можно попасть пря и > 1 с вероятностью -' или прн п = 1 с вероятностью О. Вероятность попадания в интервал (и — 1, и) равна 11/2'~ — 3/2»з»з для 1 < С < и-1. (Этими значениями будут —, », лез .., ..) Вероятность попадания в интервал (1,п) при и > 1 равна 5/2» ы — 3/2з" ; вероятность попадания в интервал (О,п) равна 3/2" — 1/2»" » Здесь: после соответствуя»дях усилий (лаял). — Прим.
я»ров. Случай у, т > и + 2. Вероятности, полученные для этого случая, приведены в следующей таблице. Единственная особенность этих результатов, которая обращает на себя внимание, заключается в том, что они чрезвычайно неупорядочены. Именно это обстоятельство делает их неинтереснымн. 21. Покажите, что при фиксированном «и при 2 < в < 2 + для больших т кав!дый цикл "вычитание и сдвиг" рассматриваемого алгоритма уменьшает (13 и) в среднем на два.
22. После вмпслнения операции сдвига вправо числа в, лежащего в интервале 1 < в < 2~, до тех пор, пока оно ие станет нечетным, ровно для (!у — ги)2 '+» целых чисел выполняется равенство (13 в) = и!. Следовательно, (2 — Ц С=Ю Сев+ 2Х ~', (Ю-в)2" С е 1<»йя +2 ~~ (Ф вЂ” гл)(р/-и)2 ~" С + ~ (Ж вЂ” в)121" 1С„„.
19»<»<л 1<»3<л (Та же формула справедлива для Ю в обозначениях 1У!» .) Средняясуммаравна21' 12 «„ и!и2 "((а+11)!!+З-ат-/)и). Поскольку ш2-ж — 2 („+ Ц2'-» н е« » гл(т — Ц2 ш 4 — (и +и+2)21"", ей!»<» сумма по !и равна 2 * ~! в2 "((З-а-!би+(а+/1)Ю)(2-(и+Ц2~ »)-а(4 (и~+и4.2)2' »)) а<»<!г =2эл 1~(а+/1)Ж~~! и2 "(2-(и+ц21 ")+О(ц). »йе Таким обрезом, в ответе коэффициент при (а+ !3)Ф равен 2" (4 — ( ! ) ) = 111. Замечение.
Точное значение сумм может быть получено после ряда скучных вычислений на основе общей формулы суммирования по частям; 1»! '» З Н„-.э»+Ь з. ""-=-Й=- (1 з)!»+1 (1 х) +1 ейь<» ь»л 23. При х < 1 выполняется соотношение Рг(в > «и «/и < х) = -'(1 — С„(х)). Если же х > 1, то -.' + Рг(н < «и «/в > 1/х) = -' + -'С„(1/х); в соответствии с (40) зто также равно $(1 — С„(*)). 24. Я„,э! 2 "С(1/(2" + Ц) = Ю(Ц. Это значение, не имеющее отношения к классической константе, приближенно равно 0.5432о82959. (ш — 1, и): (т-г, в) ". (иг — в, и): (т — в — г, и)! (О, и): 1/2-3/2~ "+з -б 1/2 +', 1/21+3/2т +!+! 1 < Ф < и. 1/2" + 1/2~, в > 1,' 1/2" +' + б!1/2 ', 1 < 1 < щ — и; 1/2»-1 26.
Как заметил Ричард Вреит (В!сЬзгг! Вгеис), фунггцня О(е ") — нечетная аналитиче- ская Функция лля всех вещественных значений д. Если положить О(е" з) = Лгу+ Лздз + Лзд +... = Р(е " — Ц, то получим — рг = Лг = Л, рз = -.' Л, — рз = з Л+ Аз, р« = «1Л+ ~1Лз, —,, = 1гл+,-'Аз+А.; Л» = — ~~',(Ь)-грз. (-Ц"р. = Ц" ~ — ';Л,; Приведем несколько первых значений: Лг хз .3979226812, Лз — —.0210096400, Лз ж .0013749841, Лг гв —.0000960351. Фаиигасгличсские ирздиолоохеиизг огиз»»(-Аз««г/Лзз-г) = 1/гг . 26. Согласно (39) девая часть раг«на 2о(1/х)-5о(1/2х)+25(1/4х)-2Я(х)+5В(2х) 2В(4х)' согласно (44) праиая часть равна Я(2х) — 2о(4х) + 2В(1/х) — Я(1/2х) — 2$(х) + 4В(2х)— 4л(1/2х) + 2>(1/4х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
