Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 105
Текст из файла (страница 105)
(а) Пусть Ал ж М(Ф вЂ” 1)/(М вЂ” 1) — Е,т; тогда при АГ > 2 имеем « — М' л)Ел ы М— 1-М(1 — 1/М)л '+М' л 2 о<вся (' )(М-1) "Ев. Поскольку М вЂ” 1 > М«-1/М)л"', по индукции находим, что Ел > О. (Ь) По теореме 1,2,7А при х = 1/(М вЂ” 1) н и ж Е -1 находим Рл =аи+М' ' 2 „( )(М-1) Рв,гдеаг =ОиО < ал < М«-1/М)' /1оМ < (М вЂ” 1)э/М 1и М при Аг > 2, Следовательно, 0 < Рл < (М вЂ” 1) Ал/М 1п М < (М вЂ” 1)(Х— 1)/1п М. 26. Приняв 9 = 1, в = — ' во втором тождестве упр, 5.1, 1-16, получим 1/3-1/(3.
7) +1/(3. 7 15) — ы 0.28879; несколько удобнее использовать в = — -' и взять половину полученного результата. Можно также применить формулу Зйлера вз упр. 5.1.1-14, включающую только отрицательные степени двойки. (Джон Ренч (ЛоЬв %геосЬ) вычислил это значение с точностью до 40 десятичных цифр: 0.28878 80950 86602 42127 88997 21929 23078 00889+.) 27. (Ради собственного удовольствия доведем точность релпения до 0(Аг ').) В обозначениях нз упр.
5.2.2-38 и 5.2.2-48 имеем $л+~ (2" ") (1 — 2"м)л Сл = Ул + Ж вЂ” 1+ — ' — аЛ вЂ”;У+ ~ (-1)" 2 "ы+нг~ Я+1 й,",«-2- ) где и = 2/« . 1) — 4/(3 3. 1) + 8/(7 7 3 1) - 16/«5 15 7 3 1) + 1.60669 51524 15291 76378 33015 23190 92458 04806 —, а,3=2/«3 1) — 4/(3 7.3 1)+8/(7 15 ° 7.3 ° 1) — ° 0.60670. Зтичисленныеоценки приводят к выводу, что и = Е+ 1, т. е. к факту, который нетрудно доказать. Значение (2' ")™(1-2 м)» равно О(йу' ) согласно упр. 5,2.2-46; а ел+1/(Х+1) = У»сы — Ул. >о Следовательно, С» = ул+г — (а — 1)!Э' — а+ О(лу ') = (ну+ 1) 18(Ю+ 1) + йг((7 — 1)/!и 2+ э — а+ 6-~(йу)) + 1г — 1/!п4 — а — э61(Х) + О(ур ') согласно упр.
5 22-50. Отклонение длины вкутроннего пути дерева цифрового поиска было вычислено в работе К!гзсЬепЬо(ш, Ргог!!пбег, апг) Яграпйоиэй), Я1СОМР 23 (1994), 598-616. 28. Выкладки в тексте и упр. 27 применимы для любого М > 2 — следует только подставить М вместо 2 в соответствующих, вполне очевидных местах. Следовательно, среднее количестао проверок цифр при случайном успешном поиске составляет Сл/йг = (ул+1-ам+1+О(а" ') = !обм !7+(7-1)/!и М+-' — ам+6-1(Ж)+(!обм а)/ну+О(Х '); при неудачном поиске оно равно Слт~ — С» = Рл+э/(йг+ 2) — ам + 1+ О(!р ') = 1ой»г !т+ у/1п М+ 1 — ам — 6о(!т+ 1) + О()7-'). Здесь 6 (и) определена в упр.
19, а ам = ~ ~(-1)УМгы/(Мз+' — 1)г(М' — 1)... (М вЂ” 1). Узо 29. Флажоле (Р!а]о!ег) и Седгевик (Яег)беи1сЬ) ]Я(СОМР 16 (1986), 748 — 767] показали, что среднее количество таких узлов примерно равно 0.37274 при М = 2 и 0,689!т' при М = 16. В работе Флажоле и Ричмонда (Вапдогп яггисспгсэ апгу Аубогпйтэ 3 (1992), 305 — 320] приводтся обобщение этого резучьтата.
30. Итерируя рекуррентное соотношение, получаем Ьв(г) в виде суммы всех возможных членов вида 31. Ь'„(1) = гщ см. у~р, 5.2.2-36, (Ь). (Дополнительную информацию о дисперсии и предельных распределениях М-арных обобщений деревьев метода "Патриция" можно найти в роботах Р. К!гэсЬепЬоГег апов Н. Ргог!щбег, Ъгктпге Хост 1п Сощр. Ясб 236 (1986), 177-185; Чу. Ягрвпйоиэй), 6АСМ 37 (1990), 691-711; В. ВлЬ, Р, Ласт!пей апб Ч'. Яэрапйоиэй(, Я(АМ Х В!эстесе ЛХМЬ.
6 (1993)„197-213.] 32. Сумма полей 381Р равна количеству узлов в соответствующем бинарном дереве, поэтому ответом является величина А» (см. упр. 20). 33. Вот как была получена формула (18). А(2г) -2А(г) = ег* -2е'+1+ А(г)(е* — 1) может быть приведено к виду А(2г)/(ег* — 1) = (е* — 1)/(е' + 1) + А(г)/(е* — 1). Следователыю, А(г) = (е* — 1) 2, > (е'У~ — 1)/(еьа + 1). Теперь„если /(г) = г с г", то г .>, /(г/21) = 2 с г"/(2" — 1). В нашем случае /(г) = (е* — 1)/(е + 1) = гапЬ(г/2), что эйвивазентно 1 — 2г '(г/(е* — 1) — 2г/(ег' — 1)) = 2 „>, В »гг"'(2> ы — 1)/(и+ 1)!.
Дальнейший вывод очевиден. 34. (а) Рассмотрим ~ >,~ "„'(„")Во/2до ц; согласно упр. 1.2.11,2-4 1" ' + . + (т— 1)" ' = (В (т) — В )/и. (Ь) Пусть Я„(гл) = 2',",~(1 — Ь/т)" и Т„(т) = 1/(евУ вЂ” 1). При Ь < гп/2 имеем е о"ум > ехр(п!п(1 — Ь/т)) > ехр(-Ьп/т — Ьгп/тг) > е "»"у (1 — Ьг/тг). Значит, (1 — Ь/т)" = е ~'"у"' + О(е о"у . Ьгп/тг). Поскольку Я„(т) = ~~™~, (1 — Ь/т)" + О(2"") и Т„(т) = ~„~'~ е ~"у +О(е юа), имеем Я„(т) = Т»(т)+О(е""у и/т ). Сумма членов О(ехр( — и/2')и/2гг) равна О(п '), так как сумма при 6 < !бп имеет порядок и '(1+ 2/е + (2/е)г +, а сумма при у > !бп — порядок и '(1 + 1/4 + (1/4) + (с) Доказательство аналогично доказательству, приведенному в разделе 5.2.2 при ]з] < 21г; затем используется аналитическое продолжение.
(с)) -' 18(п/э ) + у/(2 !п 2) — -" „+ 6(п) + 2/и, где 5(и) = (2/!в 2) 2 >,В((( — 2|г|/|/!и 2)Г( — 2згзй/!и 2) ехр(2хзй!Бп)) = (1/1п 2) 2 „>, БС(с(1+ 2ксй/!и 2) ехр(2язй !Б(п/к)))/совЬ(язй/!я 2) Дисперсия и высшие моменты были вычислены В. Шпанковским (зз1з. Яхрапйозве!з!),,7АСАГ 37 (1990), 691-711.
Зб. Ключи должны иметь внд (аОЬБО|«з, а0|31|ст, а1-~0«зз, а17150|«4, п17151ьзь), где а, |У,... есть строки из нулей и единиц; ~а! =- а — 1, (/1~ = Ь вЂ” 1 и т. д. Вероятность того, что пять слу- чайных ключей имеют такой вид, равна бз 2 -зьь-зь -зьь-з/2«ььь«+ьь«ь«ь ь«ьг+«+«+е бз/24«+ь+з«+«+ь 36. Пусть и — число внутренних узлов.
(а) (и!/2') П(1/э(х)) = и! П(1/2'|*| 'з(я)), где Г " длина внутреннего пути дерева. (Ь) ((и + 1)!/2") П(1/(2'|*| — 1)). (Рассмотрите суммирование ответа к упр. 35 по всем а, Ь, с, з( > 1.) 37. Наименьшая модифицированная длина внешнего пути равна 2 — 1/2л и достигает- ся только в случае вырожденного дерева (длина внешнего пути которого максимальна). (Можно доказать, что наибольшая модифицированная длина внешнего пути достигается тогда и только тогда. когда все внешние узлы расположены не более чем на дв»х смеизиых уровнях! Однако дерево с меныпей длиной внешнего пути не всегда имеет ббльщую модифицированную длину внешнего пути.) 88.
Рассмотрите подзадачу поиска деревьев с А узлами с параметрами (а, |Т), (а,-з8),..., (п,2» "8), 39. См. М|уа1|ажа, 1пЪа, ЯпБ!со, апз( НовЫ, ЯТСОМР 6 (1977), 201-234. 40. Пусть зз|/г - — истинная длина периода последовательности. Построим дерево, по- добное дереву метода "'Патриция", с аоа|...
в качестве массива ТЕХТ и с з»/г ключами, начинающимися с позиций О, 1,..., з»/г — 1. (В соответствии с выбором г ни один ключ не является началом другого.) Включим в каждый узел поле 312Е, в котором содержится количество помеченных полей ссылок в поддереве, лежащем ниже этого узла. Для выпол- нения указанной операции используйте алгоритм Р. Если поиск неудачен, ответ — 0; в случае успешного поиска и у < и ответ — г. И наконец, если поиск успешеи и / > и, ответ равен г 312Е(Р) . 43.
Ох|идаемая высота асимптотически приближается к (1 + 1/ь) !оБьз з|з с отклонением 0(1), (См. Н. Мепз!е!ьоп, 1ЕЕЕ Тгелзассзопз ЯЕ-8 (1982), 611-619; Р. Р!в)о!ес, Асса 1пуоппа|- Ыа 20 (1983), 345-369; !.. Ое|тоуе, АсСа 1п/оппаьзса 21 (1984), 229-237; В. Р!|ее!, А|Ьапсея зп Арр!вес( Ргобаййз|у 18 (1986), 139-155; «Ъ'. Яхрап!|оивЫ, А!Богзьйтзсв 6 (1991), 256-277.) Средняя высота случайного дерева цифрового поиска с АГ = 2 асимптотически при- ближается к !8 и + |/2 !8 и (А!|1опв апз! ЯЬзеЫв, Ргобабз!згу Т'Ьеогу апз! Не!аьез! Рзе!з!з 79 (1988), 509 — 542); то же самое справедливо и дпя случайного дерева метода 'Патриция" (Р!сье! апз! КпЬ!и, уоигпа) оГ Соп|бзпаго|йа! Т1|еогу Абб (1990), 292-312). 44.
См. ЯООА 8 (1997), 360-369: такая структура поиска тесно связана с алгоритмом быстрого многоключевого поиска, обсуждавшимся в ответе к упр. 5.2.2-30. Ж. Клемент (1. С!с|пепе), Ф, Флажоле (Р. Р!а)о!ес) и Б. Вали (В. Ра!!ее) показали, что при тернарном представлении поиск по лучу выполняется примерно а три раза быстрее, чем при испсиьзо- вании бинарного представления (2), с учетом доступа к узлам (см, ЯООА 9 (1998), 531 — 539). 45. Вероятность (ТНАТ, ТНЕ, ТНТБ) перед (301ЬТ, НООБЕ, 13. ХАСК), (НОННЕ, 13,ЛАСК) перед (3011,Т), (НООБЕ, 13) перед (ХАСК), (13) перед (НООБЕ), (Т!ПБ) перед (ТНАТ,ТНЕ) я (ТНЕ) пере|| (ТНАТ) равна у ' | ' ы' ' ы' = ье.
ь ы | | РАЗДЕЛ 6.4 1. -37 < г!1 < 46. Таким образом, в ячейках памяти, предшествующих ТА91.Е и следующих за ТА81.Е, не должны содержаться данные, которые соответствуют аргументу (например, их первый байт мог бы быть нулевым). Очевидно, что было бы штаха хранить К в таком лиапозоне1 (Значит, можно сказать, что метод из упр. 6,3-4 использует меньшее пространство, поскольку границы той таблицы никогда не нарушаются.) 2. ТОМ (буксир). (В состоянии ли читатель найти десять слов из не более чем пяти букв, которые заполнят пустоты между -10 и 30?) 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
