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