Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 81
Текст из файла (страница 81)
Перси Дьяконис (Регж 1)!асов!э, РЬ. П. |Ьеэм, Нагуагд 1!туесе!гу, 1974) среди прочего показал, что определение вероятности через повторяющееся усреднение является более слабым, чем определе. ние гармонической вероятности, в смысле следующей строгой формулировки. Если !пп, 1«п !п(«, Р„,(и) = йт „!цп эцр« „Р, (и) = Л, то гармоническая вероятность равна Л.
С другой стороны, утверждение «10| < и < 10" +| для целых чисел Ь > 0" имеет гармоническую вероятность -, в то время как повторяющееся усретзение никогда | не присвоит этому утверждению некоторой конкретной вероятности.) 18. Пусть р(а) = Р(1 ) и р(а, Ь) = Я се<, р(Ь) для 1 < а < 6. Поскольку Т ж б|о 0 Ь,о,«| 0 .. !| Т|е +э для всех а, имеем р(а) = р(10а,10(а+ 1)) вследствие (|). Далее, поскольку Р(Б) Р(28) + Р(25+ 1) вследствие (|)-(|и), имеем р(а) = р(2а,2(а+ 1)), Отсюда следует, что р(а, 6) = р(2 10«а, 2 10«Ь) для всех т, и > О.
Если 1 < Ь/а < Ь'/а', то р(а, Ь) < р(а', Ь'). Причина в том, что существуют целые числа т, «, т', и', такие, что 2~ 10" а' < 2 10'а < 2 10«6 < 2~ 10«Ь' как следствие из того факта, что !о8 2/ !об 10 является иррациональным числом; следовательно можно применить аксиому (з). (См. упр. 3.5-22, в котором нужно положить Ь = 1 и Н = «!о62/!о610.) В частности, р(а) > р(а+ 1) и отсюда следует что р(ц Ь)/р(а Ь+ 1) > (Ь вЂ” а)/(Ь+ 1 — а). (См. формулу 4.2.2-(15).) Теперь можно доказать, что р(а, Ь) = р(а', Ь'), если только Ь/а = Ь'/а'; для любого большого значения и выполняется р(а, Ь) = р(10«а, 10«Ь) < с р(10«а, 10«Ь — 1) < с«р(а', Ь'), где с„= 10«(Ь вЂ” а)/(10 (Ь вЂ” а) — 1) = 1+ 0(10 «).
Для любого положительного целого числа «имеем («) (,«! «-)+ (Ь «-|6| «-2)+ + (6«-| 6 ) ( 6) Если 10 < а«< 10 +' и 10 < Ь" < 10 +|, то р(10 +'.10 ) < р(а",Ь«) < р(10"',!О +') согласно (у). Но р(1,10) = 1 вследствие (!т); ото|ода р(10™, 10 ) = т' — и| для всех т' > т.
Приходим к заключению, что (!об,еЬ"] — (!обша"] — 1 < ир(а,6) < '1!об|о 6"] + (!обща«] +1 длн всех п и Р(а,Ь) = !общ(6/а). ]На это упражнение автора вдохновил Д. И. А. Колен (11. 1. А. СоЬеп), который доказал несколько более слабый результат в Х СотЬ!пасет!а! ТЬе|ну А20 (1976), 367-370.] 19. Эквивалентно утверждению, что ((!об 1ОР„) и|од 1) имеет равномерное распределение в смысле определения 3.5В. Поскольку 1обш Р« = «1о8104| — !об|» з/5+ 0(4| |") согласно 1.2.8-(14), это эквивалентно равномерному распределению (и!об|о|6), что следует из упр. 3,5 — 22, (Р!Ьоласс! ()оаггег!у 5 (1967), 137-140.] То же доказательство показывает, что последовательности (6«) подчиняются логарифмическому закону для всех целых чисел Ь > 1, которые не являются степенями 10 [Яглом А.
М. и Яглом И. М«Неалемеигарные звдачи в элементарном изложении (М: Гостехиздат, 1954; Епб!!эЬ сгэлз1абоп, 1964), Залача 916]. Замечание. Этим же свойством обладают многие другие последовательности целых чисел. Например, в работе Ре|э| О!асотэ„Алла)з а( РгоЬаЬ|б|у 6 (1977), 72-81, показано, что одной из них является (и!) и что последовательность биномиальных коэффициентов также подчиняется логарифмическому закону в том смысле, что 1 Еш — ) (10~( ) < г) = 1об,е г. в-«ьа и+ 1 ь ь=е В работе Р. Ызаще, Магй. )засйгзсйгеп 143 (1990), 137-144, доказано, что знаменателзз в непрерывных разложениях дробей имеют логарифмические дробные части, если только частичные отношения имеют повторвющуюся форму с полиномиальной вариацией, как и уцр.
4.3,3-16. Очень интересен вопрос, который до сих пор остается открытым; будет ли последовательность (2!, (2!)!, ((2!)!)!,... ) иметь логарифмические дробные части; см. 1. Н. Соаиау и М. 1. 'Г. Оау, Баге)щ 23 (19б2), 13-19. РАЗДЕЛ 4.3,1 2. Есзи з-м слагаемым является а, = (ац„п...а,защ)ь, то используем алгоритм А, в котором швг А2 модифицирован следующим образом. АЗ', (Сложить разряды.) Присвоить щз «- (азу+... + а,лз + Ь) шо«(Ь и й+- ((аз« + + апз + й)/Ь).
Сбросить индикатор переполнения, Ь+- О. (гХ щ следующее значение к.) (ЫС(а«з ) ш 0 + и(з — 1) + 1.) гА «- гА+ а;, Перенос единицы. Повторить для зи > з > 1. (НЗ щ и(з — 1) + 1.) а«, «- гА. Повторить для О < у < и. Запах«нить последний перенос в щв, $ Время вьшолнения в предположении, что К = -'МЖ, равно Ь.ЬМ««Г + 7Л«+ 4 циклов.
4. Перед шагом А1 можно сделать следующее утверждение: "и > 1 и О < а„е, < Ь при О < з < и'. Перед шагом А2 справедливо утверждепне '"0 < 1 < и; 0 < аи и, < Ь при 0 < з < и: 0 < щ«< ЬприО < з < у; 0 < Ь < 1; (из-з .. ае)ь+(а;-«ее)ь = (аиз-з ..ще)ь". Более точная форма последнего утверждения такова: е<«<1 е<«<з Перед шагом АЗ справедливо утверждение "0 < у < и: О < а«,а«< Ь при О < з' < и: 0 < щ; < Ь нрзз О < з < у; 0 < Ь < 1 и (а;... ае)ь+(аз...
гв)ь = (Ьщз .., що)ь". После шага ЛЗ справедливо утверждение, что 0 < щ«< Ь при О < з < и; 0 < аы < 1 и (а з ... ае)ь + (а„з... ее)ь = (щ„... юе)ь. После етого можно довольно просто закончить доказательство, проверив справедливость нужных импликацнй для утверждений и показав, что выполнение алгоритма всегда завершается. (Максимальное значение й 3. ЕИИ1 И 1 10« ОРЬО 1 ЕИТХ О 1 2н 31ах 5 ж ЕИТЗ Ньй,1 А« ЗЕ ХОО 0,3 МЛ« УИОУ ь+2 МЖ 1ИСХ 1 К ОЕСЗ И МЛ« ЗЗИИ ЗВ МАГ ЗТХ И+И, 1 ку 1ИС1 1 Л« 313 2В «1« ЗТХ И+И 1 равно зи — 1„позтому при из > Ь потребуетск изменить шаг АЗ.) б. В1.
Присвоить у»- и — 1. вь, »- О, В2. Присвоить 1»- ву + е, ю»».'— 1 пюй Ь, » +- у'. ВЗ. Если С > Ь, присвоить» с- »+ 1, » +- вь + 1, ю, +- 1 пюй Ь и повторять этот шаг до тех пор, пока не будет выполнено неравенство С < Ь. В4. Уменьшить у ца единицу и, если / > О, вернуться к шагу В2. $ 6. С1. Присвоить у+- и — 1, »+- и, г+-О. С2. Присвоить 1+- и, + в . Если 1 > Ь, присвоить ш; +- г + 1 и ю» +- О прн» > Ь > й; затем присвоить» +- у и г +-1 п»ой Ь.
В противном случае, если 1 < Ь-1» присвоить вь +- г и иь»- Ь - 1 при» > )с > у. После этого присвоить» +- у и» с- Е СЗ. Уменьшить й нв единипу. Если у > О, вернуться к шагу С2, в противном случае присвоить ю; +- ». и в»ь» — Ь вЂ” 1 при» > й > О. $ Т.
Если, к примеру, у = и-3, то»с = О с вероятностью (Ь+ Ц/2Ь; Ь = 1 с вероятностью ((Ь вЂ” Ц/2Ь)(1 — 1/Ь), а это вероятность того, что произошел перенос и предшествующий разряд не был равен Ь вЂ” 1; Ь = 2 с версжтностью ((6 — Ц/2Ь)(1/Ь)(1 — 1/6) и )с = 3 с вероятностью ((Ь вЂ” Ц/2Ь)(1/Ь)(1/6)(Ц. При фикс»»рованных Ь можно щюсуммирааать все вероятности по параметру у.
ко»орый изменяется от и — 1 до О; это даст среднее число случаев, когда перенос распространяется на )с разрядов: Ь вЂ” 1/ иц = — [ (и+ 1 — )с)»11 — -) + — [ . 26 Ь) 6) Для проверки найде»» среш»ге число переносов »и» + 2ш2 + ° + и»и„= — и — — ~1 6-1[ ~6) )) ч»о согласуется с формулой (6). 6. ЕМТ1 И" 1 1 ЗН ЕОА Ы,2 К 30Ч ОР10 1 1ИСА 1 К ЯТЕ М+М 1 ЗТА М,2 К 2Н ЕОА 0,1 А» ТИС2 1 К АОО Ч 1 Х ЛЗЧ ЗВ К ЗТА М1 Х 46 ОЕС1 1 Х ЛСОЧ 4Е Х ЗАЕМ 26 А» ЕНТ2 1,1 б Время выполненив программы зависит от б — числа позиций, в котора»х и + е; > Ь, и от К' — общего числа переносов.
Нетрудно заметить, что А — это та же самая величина, которая псжвляется в программе А. Анализ в тексте раздела показывает, что среднее значение б равно Х((Ь вЂ” Ц/2Ь), а среднее значение К реево 1»(»У — Ь ' — Ь с — .. — 6 "). Таким образом, если пренебречь членами порядка 1/Ь, время выполнения программы будет равно Ох+ б+ 7К+ 3 ж 13АС+3 циклам. 9. На шаге А2 везде заменить "Ь" на "Ь,", 10. Если поменвть местами строки 06 и 07, то почти всегда можно получить переполнение.
При этом ре»"истр А в ходе выполнения команды в строке 08 мовсет иметь отрицательное значение, так что программа работать не будет. Если поменять местами строки 06 н 06, то последовательность переполнений, происходящих в ходе работы программы, будет е некоторых случаях иной, но программа даст правильный результат. 11. Эта задача равносильна задаче лексикографического сравнения цепочек; (») присвоить у +- и — 1; (Н) если и < и;, закончить с результатом [в < е[; если в, = е, и 2 = О, закончить с результатом (и = е); если иг ж е и у > О, присвоить г +- г — 1 и повторить (5); если иг > в1, то закончить [и > е).
Этот алгоритм оказывается довольно быстрым, так как обычио очень мала вероятность того, что у станет очень большим раньше, чем возникнет случай, когда и, 14 е,. 12. Используем алгоритм В при иг = О и вг = и~з, В конце этого алгоритма появится другое "заимствование", ио иа этот раз им можно пренебречь. 13. ЕИИ1 И 1 ИОЬ У )У ЗТА И+И, 1 )У ЛОУ ОУЬО 1 ЗЬС 5 )У 1ИС1 1 )У ЕИТХ 0 1 йЮ СЬЗЕТ )У 11И 28 Ю 28 ЗТХ СХХЗТ Ю ЛИОУ о+2 )У ЗТХ И+И 1 $ ЬРА О+И,1 Ю 1ИСХ 1 К Время выполиеиия программы равна 2367+ К+ 5 циклам, а грубая оценка К есть -')У. 14.
Ключевым является индуктивное утверждение, которое должно быть справедливым в начале шага М4. Все остальные утверждения легко выводятся из этого утвервсдения, которое выглядит так: О < г < пг; О <,у' < и; 0 < иг < Ь цри 0 < 1 < ии О < ег < Ь при 0 < 1 < и; О < гег < Ь при 0 < 1 < 7' + гп; 0 < Ь < Ь; и в обозначениях, введенимх в ответе к упр. 4, (шго -г .шо)в+ 66'+1 = и х (ег г ...во)ь+(ш г...ио)о х егбг. 15. Ошибка иеотрицательиа и меньше (и — 2)Ь " '.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
