Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 98
Текст из файла (страница 98)
Особое значение приобретают бережливые методы в том случае, когда результат сравнения обладает надежностью иа все 100% (см. (). Е. КиисЬ, Х ессше №ци!в Сошр. $с1 606 (1992), 61-67), РАЗДЕЛ 6.1 1. (и: ц7и; . у~. ы.ю-еь 2. $1'. ]Инициализация,] Установить Р е- РХКЗТ, $2'. (Сравнение.] Если К = КЕТ(Р), алгоритм успешно завершается. $3! (Продвижение.] Ъстаиовить Р <- (.ХИК(Р) .
$4'. (Конец файла7] Если Р )А Л, перейтн к шагу $2', В противном случае алгоритм завершается неудачно, 1 3. КЕТ ЕВС 3:6 1 ТИК ЕОС )л 2 ЗТАКТ АОА К 1 Ы1 РХВЗТ 1 2Н СИРА 0,1(КЕТ) С уЕ ЗСССЕЗЗ С и)1 0,1(АХИК) С-$ )1И2 2В С вЂ” Я РАПЛВЕ ЕОО е 1 — $ $ Время выполнения равно (6С - 3$+ 4)и. 4, Да, если можно усзановнгь КЕТ(Л) равным К (Впрочем, метод дублирования цикла из программы (»' в атом случае не даст шшаких преимуществ.) 6, Нет, программа (» всегда выполняет не меньше операций, чем программа (»'.
6. Замените команды строки 08 командами ЗЕ а+4; СИРА ЕЕт+И+2,1; л)е ЗВ; ХНс1 1, а команды строк 03 и 04 — командами ЕИТ1 -2-И; ЗН ХИС1 3, 7. Заметьте, что Сл = -'Сл-~ + 1. 8. Формула суммирования Эйлера лает м(Ю С( ) и 1 — тх — Взх(х+ 1) — - О( (1 — х) 2 2! 3! (Из теории функций комплексных переменных известно, что ((х) = 2~я* 'вш(уях)Г(1 — х)С(1 — х). Эта формула наиболее полезна при х < О,) 9. (а) Да; Сл = злз — злз вН(- з( злз+ 1 злз-вН(ч ! ввН+ з +О(Аз"~). (Ь) Ся =;в (1+5(/(! — (~.в))) = Яз(Н+Н' ~/Г(! — 8)+1)+О(Н' ы). (с) При 9 < 0 (11) не является распределением вероятностей; (1б) ззает оценку Сл = — — „',Г(1 — В)Н(+в+О(А» ы)+О(П (15).
10 рз « Рл; (максимальное Сл) = (Ж + 1) — (минимальное Ся). (Аналагичмо в записях с переменной длиной максимальное среднее время поиска равно Ьз(1+ рз) + + Е,л (1 + рл) л»инус миннмальмое среднее время поиска.) 11. (а) Произведения ~,„-з(х»„..., хп„,)Р; представляют собой вероятмости возмякных последовательных запросов, после выполнения которых злемеит Нз оказывается на пз-м месте. (Ь) Второе тождество получается после суммирования всек (") вариантов первого подмножества на различных ял-подмножествах Х с учетом того, что каждый из ннх встречается Р л рвз.
Третье тождество является резуззьтнгом обращения второго. (5(ажно также использовать принцип включения и исключения.) (с) 2 тР, = з»ч) „— (в' („ц, а потому 4. =1+(А(-1)-Р; »' —; 1 , Рз+Рз „~, А. ~ Рз+Рз Н ~, '~ .+ ~Р~Р~' л~ ,< Р(+Рз, Р +Рз )7рвмечанве. В. Дж. Хендрикс (%. Л. Непдгю)»в) (з. Арр!зе»( РгабаЬЛйу 9 (1972), 231— 233) нашел простую формулу для финальных вероятностей каждой перестановки записей.
Например, при Н = 4 предельная вероятность последовательности Нл Вз Л» Нл равна Рл+ рз + Р»+рз р( +Р» +рз р» +Рз рл Джеймс Битмер (Затлев Вйпег) ~Я!СОМР 8 (1979), 82 — 85) доказал, что, если изначально список неупорядочен, ожидаемое время поиска после ( случайных запросов превысит Сл ма величинУ з 2т, .(Р,-Рз)~(1-Р,— Рз) 7(Р(+Рз). Такам обРазом, дла ! поисков потРебУетса в среднем менее (Сн + -'), (Р1 — Р )л/(Р~ + рз)» < (Сл + -з(з) сравмений.
См, также доюлзатвльство с применением производящих функций в работе Р. г'!а1о!есз Р. л»агбу, апс! Ь. ТЬ»шоп!ег, Пйсге»е АРРЬе(( МаП». 39 (1992), 207-229, 18. 12. Ся = 2 ~ + 22 ~ а 1(з(2 + 1). Эта выражение быстро сходится к 2а' вз 2.5290; в упр. а.2.4-13 дано зйачение а' с точностью до 40 знакож 13. После выполнения весьма утомительного суммирования п(п+ 1)(2п+ 1) п(п+ Ц(10п — 1) Н„,л = зл Зб л=з получим ответ: Ся = з"" - з(2Н+ 1)(Н». — Н-) +» — з Р'+ ') ' = 409АЬ 14.
В предположении, что хз < тз « х„, максимальное зиа»ение достигается при р з < р»л « ''' У»„и минимальное — п(зи 9»з » ° р»„. Рассуждения аналогичны рассуждениям при доказательстве теоремы Б. 15. Рассуждая так же„как в теореме Б, можно прийти к выводу, что расположение Из Нз... зЬт оптимальна тогда и только тогда, когда Рз(»Е((! — Рз) » Ря(»Ья(1 — Рл). 16.
ОжидаемоевремяпроверкиТ~+р~Тт+р~рзТз+ +руре . рл-~Тл минимальнотогда и только тогда, когда Т~/(1 — р~) < . < Тт[(1 — рл). [ШТ 3 (1963), 255 — 256; некоторые нмтересные дополнения получены Джеймсом Р. Слейглом (»ашгв К. Я)ай(е), »АСМ 11 (1964), 253-264.] 1Т.
Выполняйте задания в порядке увеличения их крайних сроков выполнения — независимо от значений Т;! (Естественно., в реальной жизни одмн зе,тания важнее других и требуется мнмимизировать максимальное взвешенное запаздывание; возможно, придется минимизировать сумму 2,',", шах(Т„,+ +Т,, — Р„.,О). Похоже, однако, что простого решения для таких постановок задач не существ»чтг) 18. Положим Ь = 1 при наличии в и Ь = 0 в противном случае.
Пусть А = (» [ 9» < г~), В = (» [ д, = г,), С = (» [ 91 > г1), 1» = (» [ 11 > О); тогДа сУмма 2', Р,Р~бн д длЯ расположения (д, г) минус соответствующая сумма для расположения (9', г') будет равна 2 ~ (рд ш?(Ф гз)(бпчй — бь $+гь-а-у)+2 )~' (Я, — г;)гз(4л+тъ-,+з — А-ве»). ША,»ЕС 'ес,зео Эта величина положительна, за исключением случаев, когда С = 9 или А1»11 = 9.
Искомый результат следует из юго, что расположения в виде "оргвмных труб" — единственмые располоисення, которые не могут быть улучшены таким способом (и с помощью его зеркального двойника) при т = О, 1. (Этот результат получен Г. Г. Харди (С, Н. Нагду), Дж. Э. Литлвудом (». Е. ьййемооб) и Д. Пойа (С, Рб1уа) [Рюс, Ьопдоп МасЬ. Бос. (2), 25 (1926), 265-282[, которые показали, что минимум Ь,', р,д,4Ь,~ достигается для всех независимых перестановж р н 4 только при "органном порндке" р н Ф Более подробные разъяснения н обобщения можно найти в их книге 1педиаЕпее (СшпЬгн18е Нштегв1су Ргглз, 1934), СЬарсег 10.) 19. Все расположения одинаково хороши.
Считая, что Ы(», ») = О, находим рр„4(Ь») = -' ~ р,р,(г((1,») + Щ,1)) .= фс. (Частный шгучай 4(1,») = 1+ (» — 1) шос? А' для 1 ~ » был рассмотрен К. К). Айверсоном (К. Е. 1тегзоп) в работе А Рюбгапип!пб Ъшцпайе (Не» Уог1п 'гт(1еу, 1962), 138. Р. Л. Бейбер (К. 1.. ВаЬег) в работе»АСМ 10 (1963), 478-486, изучил некоторые задачи„связанные с поиском на лемте с возможностью чтения, перемотки илн возврата на Ь блокге без чтения. В.
Д. Фрейзер (%, П. Ргакег) нашел, что возможно значительное ускорение поиска в случае репликации в файле некоторой информации. В работе Е. В. Е?сЬе1Ьегбег, 1т'. С. Кодбегз, апс) Е, %. агапу, 1ВМ». ЕшеагсЬ 4г 1»ете1ортепг 12 (1968), 130-139, имеется змпирическае решение схожей задачи.) 20. Переходя, как и в упр. 18, от (д, г) к (4', г'), получим нзменемие (Ф вЂ” г )(Ъ вЂ” 1)(г(р-Л вЂ” й(п(г1ь+ - -;,йге» вЂ” )), <еА,тес которое всегда положительно, кроме случаев, когда А или С является пустым мможеством. Вследствие циклической симметрии оптимальные перестановки представляют собой циклические сдвиги "органной" комфигурации.
(О другом классе задач с тем же ответом можно прочесть в работе Т, Я. МоЫпп апг) Е. С. Бегапэ, Ргос. Ашш.. Май. Яос. 7 (1956), 1014-1021.) 21. Эта задача впервые была решена Л. Х. Харпером (Ь. Н. Натрет) [ЯХАМ»..4рр1. МагЬ. 12 (1964), 131 — 135[. Обобщении и ссылки на другие работы можно найти в», Арр1юд Рюбаб))йу 4 (1961), 391-401. 22.
Приоритетная очередь размером 1000 злементов (представленная, например, в виде кучи; см, раздел 6.2.3). Всшвьте в очередь первые 1000 записей, причем элементы с Большими значениями 8(К1, К) вставляются в начало очереди. Затем каждым последующим к,, для которого ы(кз, к) < 4начало очереди, к), следует заменить первый злемент очереди и переупорядочить ее. РАЗДЕЛ 0.2Д 1, Докажите по индукции, чтопридостнжениишаха В2 К~ 1 < К < К«ю ичто1 < 1 < н при достижении шага ВЗ, 2. (а, с) Нет; алгоритм зацнклнтся при 1 = н — 1 и К > К„. (Ь) Да.
Однако при отсутствии в таблице К он будет зацикливаться при 1 = и и К < К . 3. Это алгоритм 6. 1Т прн Х = 3. При успешном завершении поиска алгоритм выполняет в среднем (Х+ 1)/2 сравнений; в противном случае среднее число сравнений составляет Ж/2+ 1 — 1/(Ж+ 1). 4. Это должен быть неудачный поиск с Ж = 127; следовательно, согласно теореме В ответ равен 138н. 6. Среднее время работы программы 6,1(4' составляет 1.76Ф+ 8.6- (Х шой 2)/4М; таким образом, она опережает программу В тогда и только тогда, когда Х < 44. (Программа С проигрывает при Х < 11.) Т.
(а) Определенно, нет. (Ь) Примечания в скобках в алгоритме И остаются справедливыми, а потому алгоритм будет работать, но только если при нечетном Ж ключи Ко = -оо и Кле1 = +ос будут присутспюеать в таблице. 8. (а) Х. Интересно доказать зто по индукции, заметив, что при замене Ю на Х + 1 увеличивается ровно одно из приращений д. (В л ЧМ 77 (1970), 884, можно найти обобщение етого утверждения.) (Ь) Максимум = 2, 8 = К; минимум = 261 — 2 . д, = Ж шо02. й. Тогда н только тогда, когда Х = 2" — 1. 10. Используйте "макрорасширение" программы, содержащей таблицу РЕЬТА. Так, для Х = !О получим следующее.
БТ БИТ ЕИТ1 6 РРА К СИРА КЕТ,1 Л СЗА С4А 1$ БРССЕББ СЗА Е00 1ИС1 3 РЕС1 3 СИРА КЕТ,1 СИРА КЕТ,1 Л СЗВ ЗСЕ С48 С48 1$ БРССЕ$$ СЗВ ЕРР 1ИС1 1 РЕС1 1 СИРА КЕТ,1 СИРА КЕТ. 1 Л. СЗС УОЕ С4С С4С ЗЕ БРССЕББ СЗС ЕЕР 1ИС1 1 РЕС1 1 СИРА КЕТ,! СИРА КЕТ,1 ЗЕ БРССЕББ ЗЕ БРССЕБЯ ЗИР РА ПЛИЕ ЗИР РА1УЖЕ 3 (В упр. 23 показано, что болыпинство команд 1$ можно исключить, получив в результате программу из примерно 6 18 М строк, которая выполняется за около 4 1Б Ф единиц времени. Однако такая программа окажется быстрее только для )т* > 1000 (приблизительно).) 11. Рассмотрим соответствующее дерево (например, такое, как на рнс, б): при нечетном !т левое поддерево корня представляет собой зеркальное отражение правого поддерева и К < К; встречается так же часто, как н К > К!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
