AOP_Tom3 (1021738), страница 200
Текст из файла (страница 200)
(Этот результат получен Г. Г. Харди (С. Н. Нахбу), Дж. Э. Литлвудом (1. Е. 1 ссс(е~чоос() и Д. Пайа (С. Ро(уа) (Ргос. Ъопгсоп МаВь Яос. (2], 25 (1926), 265-282), которые показали, что минимум 2",, рпЬО!, . достигается для всех независимых перестановок р и у только при "органном порядкеч р и д. Более подробные разъяснения и обобщения можно найти в их книге !леона!!Нее (СашЬгссС8е Оп!четв!Су Ргещ, 1934), СЬарсег 10.) 19. Все расположения одинаково хороши. Считая, что гс(Л !) = О, находим у рср!3(г) у) = 1'',г,р,р,(а(с,у)+с!(уЛ)) = —,'с. (частный случай гс(1, !) = 1 + (! — г) пгос! !сс для г ~ !' был рассмотрен к.
1О. Айверсоном (К Е. 1чегвоа) в работе А Ргобгыпт!л8 ! албпабе (Хелч Ъ огус Ж!)еу, 1962), 138. Р. Л. Бейбер (Н. 1. ВаЬег) в работе АЛСМ 10 (1963), 478-486, изучил некоторые задачи, связанные с поисколг на ленте с возможностью чтения, перемотки или возврата на !с блоков без чтения. В. Д. Фрейзер (сз'. Р. Ргвхег) нашел, что возможно значительное ускорение поиска в игучае репликации в файле некоторой информации. В работе Е. В.
Е!ЕЬе!Ьегбег, СЧ. С. Нойбегз„ апс! Е. чч'. Бсасу, !ВМ !. Вевеагс!г 3с Рече!оршевг 12 (1968), 130 — 139, имеется змпирическое рещение схожей задачи.) 20. Переходя, как и в упр. 18, от (9, г) к (9', г'), получим изменение (9, — г*)(д, — г )(г!р,! — гп!н(г!л~глгл с мс!,Аг г)), ~Ел,гЕС которое всегда положительно, кроме случаев, когда Л или С является пустым множеством. Вшгедствие циклической симметрии оптимальные перестановки представляют собой циклические сдвиги "органной" конфигурации.
(О другом классе задач с тем же ответом можно прочесть в работе Т. 8. Мосгйш апб Е. С. Я!гааз, Ргос. Лшег. МаСЬ, Вас. 7 (1956), 10)4-1021.) 21. Эта задача впервые была решена Л. Х. Харпером (1 . Н. Нахрег) (ЯАМ з'. Арр!. МаСЬ. 12 (1964), 131-135). Обобщения н ссылки на другие работы можно найти в Х Лрр!)ес( РгоЬа!г!!(су 4 (1967). 397 — 401. 22.
Приоритетная очередь размером 1 000 элементов (представленная, например, в виде кучи; см, раздел 5.2.3). Вставьте в очередь первые 1 000 записей, причем элементы с большими значениями 8(Км К) вставляются в начало очереди. Затем каждым последующим К,, для которого Ы(Км К) < б(начало очереди, К), следует заменить первый элемент очереди и переупорядочить ее.
СЗА ЕОО ОЕС1 3 СИРА КЕТ,1 ЮОЕ С48 СЗВ ЕОО ОЕС1 1 СИРА КЕУ,1 УСЕ С4С СЗС ЕЦО * ОЕС1 1 СНРА КЕТ,1 ЗЕ ЯОССЕБЯ ЗИР РАПЛЕЕ 1 (В упр. 23 показано, что большинство команд ЗЕ можно исключить, получив в резулшате программу нз примерно 6 )8 М строк, которая выполняется за около 4 !К !7 единиц времени. Однако такая программа окажется быстрее только для !7 > 1000 (приблизительно).) РАЗДЕЛ 6.2.1 1.
Локажитепо индукции, что придостижениишагаВ2 Л~ ~ < К < К„т~ и что ! < ! < н при достижении шага ВЗ. 2. (а, с) Нетз юшоритм зацнклнтся при ! = и — 1 и К > К„. (!з) Ла. Однако при отсутствии в таблице К он будет зацикливаться при ! = и и К < К,. 3. Это алгоритм 6.1Т при Х = 3.
При успешном завершении поиска алгоритм выполняет в среднем (Х+ 1)/2 сравнений; в противном случае среднее чигло сравнений составляет !7(г т 1 — 1ДЛ + Ц. 4. Это должен быть неудачный поиск с 77 = 127; следовательно, согласно теореме В ответ ранен 138и. 5. Среднее время работы программы 6.16)' составлнет 1.75Х+ 8.5 — (5Г шоб 2)/4!7; таким образом, она опережает программу В тогда и только тогда, когда )7 < 44. (Программа С проигрывает при 77 < 11 ) Т. (а) Определенно„нет.
(Ь) Примечания в скобках в алгоритме П остаются справедливыми, а потому алгоритм будет работать, но только если при нечетном 7Т ключи Ко = — со и Клэ.~ — — +со будут присутствовать в таблице. 8. (а) ~У. Интересно доказать это по индукции, заметив, что при замене !7 на М+ 1 увеличивается ровно одно из приращений б. (В ЛММ ТТ (1970), 884, можно найти обобщение этого утверждения ) (Ь) Максимум = 2, б = Х; минимум = 25~ — 2 б; = 07 шоб2. 9. Тогда н только тогда, когда Тг' = 2 — 1.
ь 10. Используйте "макрорасширение" программы, содержащей таблицу ВЕСТА. Так, для Х =. 1О получим следующее БТАКТ ЕИТ1 5 СОА К СИРА КЕ7,1 51 СЗА С4А ЗЕ ЯОССЕББ 1ИС1 3 СИРА КЕТ,1 31 СЗВ С48 ЗЕ БОССЕЯЯ 1ИС1 1 СНРА КЕТ,1 УС СЗС С4С 1Е БОССЕЯБ ТИС1 1 СИРА КЕТ, 1 ЮЕ БОССЕЯЯ УИР РА11ОКЕ 11. Рассмотрим соответствующее дерево (например, такое, как на рис. 5): при нечетном 7»» левое поддерево корня представляет собой зеркальное отражение правого поддерева и К < К; встречается так же часто, как и К ) Кь В среднем, С1 = -'(С+Я) и С2 = -'(С-Я), А = — '(1 — Я). При четном Х дерево имеет тот же вид„что и при /»г+ 1, с метками, 2 уменьшенными на 1 (за исключением узла ®, который при этом становится излишним).
В среднем, полагая й = (18 Ю), имеем: С+1 Й С вЂ” 1 5 С1 = — С2 = + 2 2К' 2 2Ж' С 2(»»г+ 1) ' 2(К+ 1) А=О при Я = 1; /»» 2(Л»»-1) (Среднее значение С указано в тексте.) 13. 1»'= 1 2 3 4 5 5 7 8 9 10 11 12 13 14 15 16 Сн=1 11 12 21 21 22 2» 3 — ' 3 3 3 3» Зз Зз 3» 4 — ' 14. Одна идея заключается в поиске наименьшего М > О, такого, что д» + М имеет вид Р»э» — 1. Затем следует установиты е- Г» — М на шаге Г1 и вставить в начало шага Р2 "Если» < О, то перейти к шагу Р42 Лучшим решением будет адаптация метода Шара к поиску Фнбоначчи: если результат самого первого сравнения К ) Кг„усэановить»»- » — М и перейти к шагу Г4 (далее все продолжает работать, как обычно). Это позволяет избежать дополнительных затрат времени работы во внутреннем цикле.
15. Внешние узлы появляются на уровнях от (й/2) до 1»-1; разница между этими числами превышает единицу для всех )с, кроме 5 = О,..., 4. 18. Дерева Фибоначчи порядка /с, отображенное зеркально (так что левое и правое подде- ревья меняются местами), согласно "естественному соответствию" из раздела 2.3.2 пред- ставляет собой диаграмму размножения кроликов по )г-й месяц включительно (нвдо только удалить верхний узел диаграммы). 17.
Пусть длина пути равна й — А(п); тогда А(Р1) = у и А(5~ + и») = 1 + А(ш) при 0 < па < Р» 18. Успешный поиск: А» — — О, С» = (3/»Г»э» + (й — 4)Г»)/5(Р»э» — 1) — 1, С1» = С»»(г»вЂ” 1)/(Р»э» — 1). Неудачный поиск: А» — — Р»/Р»~.», С» = (35Р»э» + (й — 4)Р»)/5Р»+», С1'„= С»»Г»/Р»».» + Р»»/Г»+». С2 = С вЂ” С1. (См. также упр. 1.2.8 — 12.) 20. (а) 5 = р "и ". (Ь) В приведенном рассуждении, по меньшей мере, дее ошибки.
Первая состоит в том, что деление не является линейной функцией н его нельзя просто «усредиять'! В самом деле, с вероятностью р получим р»»» элементов, с вероятностью о их будет 47»», так что л»атематическое ожидание составляет (р~ + д~)Х; следовательно, искомый множитель равен 1/(р~ + о~). Теперь, когда мы выяснили, что после 7» итераций множитель равен 1/(р~ + 9~)", нельзя утверждать, что Ь = 1/(р~ +»7~), поскольку количество итераций, необходимых для поиска одних элементов, гораздо больше, чем требуется для поиска других. Это и есть вторая ошибка.
(Остерегайтесь подобных ловушек, так как зачастую в теории вероятностей ошибочные утверждения вьплядят очень правдоподобно! ) 21. Это невозможно, так как метод зависит от величины ключа. 22. Ь"ОСЯ 17 (1976), 173 — 177. См. также У. !»ег), А. Иш, а»»»( Н. Лчп1, САСМ 21 (1978), 550 — 554: С.
Н Соппес, П П. Нобегэ, ап»! Л. Л. Сеогйе, Ас»а 1л/огтабса 13 (1980), 39-52; С. Попсйегб, ВАЖО 1пЕогт. ТЬеог. 17 (1983), 365-385; Сот рис!пй 46 (1991), 193-222. Отклонение составляет О(!ой !аб»»»). Широкомасштабные эмпирические исследования Д Марсальи (С. Магзаййа) н В. Нарасимхана (В. Хасав»»пйап) (Сошрпсегэ ап»4 Ма»Ь. 28, 8 (1993), 31 -42! показали, что среднее число обращений к таблице очень близко к !8 !8»"»», плюс окало 0.7 при неудачном поиске.
При Ж = 2»о, например, для случайного успешного поиска требуется около 4.29 обращений, в то время как для неудачного . около 5.05. 23. Прн > следует идти вправо, при < . влево; по достижении узла (»), как следует из (1), выполняется К; < К < К,т» и последняя проверка покажет успешность проведенного поиска. (В таблице должен присутствовать ключ Ко = — оо.) В алгоритме С может быть изменен шаг С2, на котором можно переходить к шагу С4, если выполняется условие К = К, На шаге С3 в случае, если 0Н,ТА(7) = О, установите »» — ! — 1 и перейдите к шагу С5. На шаге С4, если 0Е.ТА [7) = О, также переходите к шагу С5, который должен выглядеть с»»едуюп»им образом: "При К = К, алгоритм завершается успешно, в противном случае алгоритм завершается неудачно".
(Такое изменение может ускорить программу С только при 7»» > 2»е; среднее время поиска при внесении изменений "уменьшается' с (8.5 !8»»» — 6) и до (8!8»»»+ 7)и.) 24. Ключи могут располагаться таким образом, что сначала будет установлено»»- 1, затем — 1» — 2» илн 2»+ 1 в зависииости от того, К < К, или К > К,. При г >»»» поиск неудачен.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
