Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 99
Текст из файла (страница 99)
В среднем, С1 = -'(С+Я) и С2 = -'(С вЂ” о), А = -'(1 — Я). При четном Ю дерево имеет тот же вид, что и при 1!!+ 1, с метками, уменьшенными на 1 (за исключением узла ( Оу, который прн этом становится излишним). В срелнем, полагая Ь = ()8 7!!), иа!еем: С+1 Ь С-1 С1= — — —, С2 = — + — „ 2 2Ж' 2 2!У' (Ь+ Ц!У (й+ Ц(!!!'+ 2) 2(Л!+ Ц ' 2(!У+ Ц при 5 = 1; Х А= приЯмО, (Среднее значение С указано в тексте.) 13. 1У = 1 2 3 4 5 б 7 8 9 10 11 12 13 14 Уб 18 Си=1 11 11 21 21 21 23 31 3 3 3 3 — '.
3-' 3 — ' 34 3 э 4 5 е г э !э !3 !4 и !6 Сл! — 1 11 2 21 2» 3 3 3$ 3!ее 3 э! Згээ 4 4 4 4 4гг' 14. Одна идея заключается в поиске наименьшего М > О, такого, что Ж+ М имеет вид Ру,.„! — 1. Затем следует установить ! +- Р» — М на шаге Г1 и вставить в начало шша Г2 "Если ! < О, то перейти к шагу Р4'! Лучшим решением будет адаптация метода Шара к поиску Фибоначчи! если результат самого первого сравнения К > Кг„, установить ! е! — М и перейти к шагу Р4 (далее все продолжает работать, как обычно).
Это позволяет избежать дополнительных затрат времени работм во внутреннем цикле. 16. Внешние узлы появлякптл на уровнях от 1я/2) до Ь-1; разница между этими числами превышает единицу для всех Й, кроме й = О,, 4. 10. Дерево Фибоначчи порядка Ь, отобра!кенное зеркально (так что левое и правое поддеревья меняются местами), согласно "естественному соответствию" иэ раздела 2.3.2 представляет собой диаграмму размножения кроликов по Й-й месяц включительно (надо товько удалить верхний узел диаграммы). 17. Пусть длина пути равна Ь вЂ” А(и); тогда А(Р ) = / и А(Р! + гл) = 1 + А(гл) при 0<т<Р, 18, Успешный поиск: Аь = О, Сь м (ЗЬРь+! + (ь" — 4)Рь)/5(Рь+! — Ц вЂ” 1, С1ь = Сь г(Рь— Ц/(Рье! — Ц.
Неудачный поиск: А'„= Рь/Рь+г, Сь = (ЗЬРь+! + (Ь вЂ” 4)Рь)/ЬРь+г, С1!ь = Сь гРь/Рьь! + Рь-! /Рь+! С2 = С вЂ” С1. (См. также упр. 1.2.8-12.) 20. (а) Ь = р вй ". (Ь) В приведенном рассуждении, по меньшей мере, дее ошибки. Первая состоит в том, что деление не является линейной функцией и его нельзя просто "усреднять". В самом деле, с вероятностью р получим р!т' элементов, с вероятностью 9 их будет 9Х, так что математическое ожидание составляет (рэ + 4~)Х; следовательно, искомый множитель равен 1/(р + д ). Теперь, когда мы выяснили, что после Ь итераций множитель равен 1/(р~+ д~), нельзя утверждать, что Ь = 1/(рх + йз), поскольку количество итераций, необходимых лля поиска одних элементов, гораздо больше, чем требуется для поиска других. Это и есть вторая ошибка.
(Остерегайтесь подобных ловушек, тах как зачастую в теории вероятностей ошибочные утверждения выглядят очень правдоподобно! ) 21. Это невозможно, так как метод зависит от величины ключа. 22. ГОС$17 (1976), 173-177. См. также У. Рег?, А.
1»в», апб Н. Ахи», САСМ 21 (1978), Ь50-554; С. Н. Соппес, 1.. ?). ??обехв, апб 3. А. Сеогбе, Асса ?п/оппагьса 13 (1980), 39-52; С. ?апсйаг»?, ИАХ?!О ?лйогт. ТЬЬог. 17 (1983), 365-385; Сошрпблб 46 (1991), 193-222. Отклонение составляет О(!об !об К), Широкомасштабные эмпирические исследования Д. Марсальи (С. Магэа81!в) и Б. Нарасимхана (В. Ьйагаэппйвп) (Сошрп!еш влд Маг!ь 26, 8 (1993), 31 — 42) показали, что среднее число обращений к таблице очень близко к !8 !8 Х, плюс около 0.7 прн неудачном поиске.
При Ж = 2ю, например, для случайного успешного поиска требуется около 4,29 обращений, в то время как дпя неудъчного — около 5.05. 23. При > следует идти вправо, при < — влево; по достижении узла Е, как следует из (1), выполняется К, < К < К,ь» и последняя проверка покажет успешность проведенного поиска. (В таблице должен присутствовать ключ Ко = -оо.) В алгоритме С может быть изменен шаг С2, на котором можно переходить к шагу С4, ели выполняется условие К = Кь На пшге СЗ в случае, если 0И.ТЬ(/) = О, установите »»- » — 1 и перейдите к шагу СЬ.
На шаге С4, осли 0И.74[у? = О, также переходите к шагу СЬ, который должен выглядеть следующим образом: "При К = К, алгоритм завершается успешно, в противном случае алгоритм завершается неудачно". (Такое изменение может ускорить программу С только при К > 2ы; среднее время поиска при внесении изменений "уменьшается" с (8.5!8% — 6)и до (818Х+ 7)и.) 24.
Ключи могут располагаться таким образом, что сначала будет установлено» +- 1, затем — » е- 2» или 2»+ 1 в зависимости ог того, К < К; или К > Кг При» > !у поиск неудачен. Например, при Ж =- 12 расположение ключей должно быть следующим: Кэ < Кэ < Кэ < Кт < Кш < Кь < К». < К» < Кш < Ке < Кз < Кв Время работы такой программы на НХХ-компьютере примерно равно б!8 ?»» единицам.
Таким образом, эта программа работает быстрее программы С, однако для начальной установки таблицы требуется известная доля труда и сообрази»ельности. 25. (а) Поскольку аа = 1 — Ьо, а~ = 2ао — Ьм аз = 2໠— Ьг и т. д., имеем А(х) + В(х) = 1 + 2хА(х). Несколько формул, приведенных в разделе 2.3.4,5, можно вывести из этого соотношения, рассматривая А(Ц, В(1), В(-'), А'(1) и В'(1). При использовании двух переменных для того, чтобы отличить шаги влево от шагов вправо, получим более общий результат А(х,у) + В(г,у) = 1+ (х+ у)А(х,у), представляющий собой частный случай формулы, справедливой для 1-арных деревьев (см.
Н. М. Катр, ЖВ Лапзас!»опз ?Т-7 (1961), 27-38). (Ь) тат(9) = ((Ь»+ 1)//Ь) твг(Ь) — ((Ьу+ 1)/Кз) шеап(Ь) + 2. 26. Дерево для трехленточного многофазного слияния, соответствующее распределению с заполненным уровнем 1с, есть дерево Фибоначчи порядка й + 1; надо только поменять правую и левую ветви. (Перерисуйте дерево на рис. 76 из раздела 5.4.4, поменяв местами левые и правые полдергвья А и С. При этом долл»ен получиться аналог рис, 8), 27. Поскольку можно упорядочить индексы таким образом, что Кп < Км « ..
К „, возможно максимум ?1+ 1 исходов из 2». Таким образом, поиск может быть описан с помощью дерева с узлами, из которьп» выходит не более (5+1) ветвей. Количество записей, которые могут быть найдены на и»-и шаге, — не более й(5+1) '.
Следовательно„среднее количество сравнений, как минимум, равно сумме )»' наименьших элементов мультимножества (й 1, !с()г+ 1) 2, )г()о+ 1)з 3,...), умноженной на Х '. При Ю ) ()о+1)" — 1 среднее количество сравнений ) (()г+ 1)' — 1) ' 2,'»»»л )г()г+ 1)' 'т ) и — 1!)с 28. (Ягг!1зег иг!К!гле ау ЪЫепьйаЬз-ЯеЫшЬез! СЬг!зз!ал!а, МагЬешагВЬ-МагпгтЫспзйаЬе!!К К!олзе (1910), Но. 8; перепечатано в ТЬое'з Яе!есгес! МазЛезпаг!сл) Рарегз (Оь!о; НштегмгегзГог!абец 1977), 273 310), (а) Т» имеет г»ьл + г»-~ = рз»/Г» листьев, (Это так называемое число Лукаса У = 4" + б",) (Ь) Аксиома гласит, чта То(Тз(х)) = Тл(х). и получается Т (Т„(г) ) = Т +,, (х) при т = 1 или и = 1.
По индукции по и результат справедлив при т = 0; например, То(Тз(х)) = То(Тз(х)»Тв(х)) = То(Тл(Тз(х))*То(Тз(х))) = То(Тз(Тз(х))) = Тз(х). И на последнем шаге следует использовать индукцию по т. 29. Пусть Ко = -со и Кл+л = Кч+з = са. 'Сначала проведем бинарный поиск на множестие Кз < Кз <; зто потребует максимум 1!6 Ж! сравнений. Если поиск неудачен, при этан определяется интервал Кзл-з < К < Кш, К отсутствует, если 21 = Х+ 2. В противном случае бинарный поиск для Кз л определит з', такое, что Кз -з < Кзу-~ < Кь. Теперь может быть два исхода — либо К = Км-л, либо К отсутствует.
(См, ТЬеог. Сокр, ,%з. 68 (1988)„67.) 30. Пусп* и = '1Х/4!. Начиная с Кл < Кз « . Кл, можно расположить Кл. Кз, ..., Кз„., в любом требуемом порядке, поменяв их местами с любой перестановкой из Кз„+л, Кз„ьз,..., Кь„ы такое расположение удовлетворяет условиям предыдущего упражнения, Теперь пусть К~ < Кз < .
< Кзгм з — границы между всеми возможными !- битовыми числами. Вставим Кз»ьл,, Кзг м„„..., Кзгы„з з между этим "частоколом" в соответствии со значениями хл, хз, ..., х . Например, если т = 4, ! = 3, хл = (001)з, хз = (111)з и хз = ха = (100)з требуемый порядок таков: Кл < Кль < Кз < Кь < Кг < Кш < Кзл < Ко < Кп < Клз < Кп (Дапус«котся также, чтобы Кз~ ггредшествавала Кло.) Бинарный поиск Кз~.~.~,,зз з в подмножестве Кл < Кз « .. Кз ю з будет эквивалентен поиску битов числа х, слева направо. (См. г !ац Манго, Хаос, БсЬзНег, ЯсЬш!ОЬ апб В!еКе1, 3.
Сснпр. Яуж. Яс1 43 (1991), 406-424.) РАЗДЕЛ 6.2.2 1. Используйте головной узел, скажем, с ВООТ ш ВЬ1ИК(ВЕКО); начните выполнять алга. ритм с шага Т4 с Р ь — ВЕИз. Шаг Тб должен выполняться так, как будто К ) КЕУ(ВЕКО) . (Соответственно в программе Т следует заменить команды строк 04 и Оо командами "ЕИ11 ВООТ; СИРА К»). 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
