AOP_Tom3 (1021738), страница 206
Текст из файла (страница 206)
и в программе 6.2.2Т, с обменом местамн гА и гХ. $ его терминальных наследников, например, по воэможности двигаясь при поиске только вправо, 12. Вставим три глучайных числа — и,(), у из диапазона [О,![ . — в изначально пустое дерево; затем удалим и с вероятностью р, Д с вероятностью д, т с вероятностью г с помощью предложенного в предылущем упражнении алгоритма. Дерево получается с вероятностью -р + э Н + -г, а это равно — только при р = О.
1 1 ! 1 13. Добавить к каждому узлу поле КЕТ и сравнивать К с этим ключом перед проверкой элемента вектора на шаге Т2. Табл. 1 должна быть изменена следующим образои: узлы (1), ..., (12) должны содержать ключи ТНЕ, АИО, БЕ, ГОН, Н1Б, 1И, ОР, ТО, НТТН, НАУЕ, НЕ, ТНАТ соответственно (если они вставляются в порядке уменьшения частоты), и зти ключи должны быть удалены из своих прежних позиций. (Соответствующая программа будет медленнее и сложнее программы Т. Волее прямолинейное М-арное обобщение алгоритма () привело бы к созданию дерева с Л узлами с одним ключом и М ссылками в каждом узле.) 14.
Если у < и, то имеется только одно такое место, а именно — КЕУ(Р) Однако при у > и множество всех появлений находится посредством обхода поддерева узла Р если имеется г появлений К в ТЕХТ, то поддерево содержит г — 1 узел (включая узел Р) и, таким образом, имеет г налей ссылок с ТАС = 1. Эти поэя ссгялок указывают на все узлы, ссылающиеся на позиции в ТЕХТ, которые содержат К (в повторных проверках ТЕХТ нет необходимости). 1б.
Начните построение дерева с установки КЕТ(НЕАО) равной первой ссылке на ТЕХТ, а также ЬЬ1ИК(НЕАО) г — НЕАО, ЬТАС(НЕАО) < — 1. Дальнейшие ссылки на ТЕХТ могут быть вставлены в дерево с использованием гледующего алгоритма. Установить К равным значению нового ключа, который гледует вставить (вто первая ссылка на массив ТЕХТ, которую делает алгоритм). Выполните алгоритм Р. Он должен закончиться неудачно, поскольку ни один ключ не может быть префиксом другого ключа. (На шаге Рб осуществляется вторая (и последняя) ссылка на массив ТЕХТ; больше ссылки на ТЕХТ делаться не будут).
Предположим теперь, что ключ, найденный на шаге Рб, согласуется с аргументом К по первым 1 бит, но отличается, начиная с позиции 1+ 1 (в которой К имеет цифру Ь, а ключ соответственно цифру 1-Ь). (Хотя при поиске с помощью алгоритма Р ключ У может стать намного больше, чем 1, можно доказать, что описанная здесь процедура найдет наилучшее совпадение с К среди всех имеющихся ключей.
Таким образом, во ессх ключах текста, которые сошщдают с К по первым ! бит, в качестве (!+1)-го бита содержится 1 — Ь.) Теперь повторим выполнение алгоритма Р, в котором К заменено его ведущими! бит (т. е. и <- !). На этот рвз поиск будет успешным, поэтому шаг Рб выполняться не будет Установите Н ~ АУА1Ь, КЕТ(Н) +- положение нового ключа в ТЕХТ. Если ЬЬХИК(Ц) = Р, установите ЬЬТИК(Ц) е- Н, ! е- 1.ТАС(Ц), 1.ТАС(Ц) +- О; в противном случае установите НЬХИК(Ц) +- Н, ! + — НТАС(Ц), НТАС(Ц) +- О. Если Ь = О, установите !.ТАС(Н) +- 1, ЬЬ1ИК(Н) е- Н, НТАС(Н) г — 1, НЬТИК(Н) +- Р; иначе установите НТАС(Н) + — 1, КЬ1ИК(Н) + — Н, !.ТАС(Н) +- г, ЬЬ1ИКОА) е- Р. Если ! = 1, установите БК1Р(Н) < — ! Ч-! — 1; в противном скучав установите БК1Р(Н) е- 1 + ! — ! + БКТР(Р) и БК1Р(Р) е- 1 — ! — 1 16. Структура дерева требует, чтобы в каждый узел входила одна идущая снизу пунктирная линия, которая начинается в той части дерева, где соответствующий ключ впервые отличается от всех остальных.
Егли такой части дерева нет, алгоритмы перестают работать. Ь(ы можем просто убрать ключи, гтужащие началом других ключей, но тогда алгоритм из упр. !4 не получит достаточного количества данных для поиска всех вхождений аргумента. 17. Если положить ао — — ао = О, то х„= а„+ ~) ( )(-1) ав/(т — 1) = ~( )(-1) вы /(т — 1). ь>г ьйэ 19. Для решения (4) необходимо преобразование а„= [и > Ц, а именно — а = [и = О]— 1 + и; следовательно, для Х > 2 получим Ал = 1 — Пл + !>щ где Пл = К(Аг, О, М) и 1'н = К(Х, 1, М) (в обозначениях из упр. 19).
Аналогично для решения (5) нужно взять а„= и — [и = Ц = а„и получить Сл = Х + гн для Н > 2. 19. При в = 1 имеем !>„= К(п, 1, т) = п((1п и+ч)/1п т- -' — бо(п — 1)) + 0(1), а при в > 2 имеем К(п, в, т) = ( — 1)*и(1/!и т + б,, (п — в))/в(в — 1) + 0(1), где 2 6,(п) = — ~ Я(Г(в — 2кей/!пгп) ехр(2я!1с!об„, и)) 1п гп ь>1 представляет собой периодическую функцию от !оба. [В этом выводе использовался тот факт, что К( +„, )/(-1)'("+') =" [ Г(')",, ~' О( '). Для малых т и в весьма малым является б (см.
упр. 5.2.2 — 45). Обратите внимвние на то, что б,(п — а) = б,(п) + 0(п ') при фиксированном а.] 20. Для случая (а) положим а = [п>в] = 1 — 6 ~~ [п =!о]; для (Ь) — ав = и— 6 ь о Й[п = Й]; в слУчае (с) тРебУетсЯ найти Решение РекУРРентного соотношениа т~ "2,'ь (")(т — 1)'" Рь пРи и > в, (з) при и ( в. Подставив х„= д„— и, получим рекуррентное соотношение рассмотренной в упр 17 формы, где а„=(1 — М ')~ ( )[пб 9]. ь=о Таким образом, используя обозначения из предьгдущих упражнений, получаем следующие ответы.' (а) 1 — Х(Х,О, М) + К(Х,1, М) — - + ( — 1)' К(Х,в,М) = Ж/(в!пМ)— Х(б-~(А!) + бе(Х вЂ” 1) + бт(А! — 2)/2 1+ + 6, а(А! — в)/з(в — 1)) + 0(1); (Ь) Х '(Х+ К(М,1, Ч) — 2К(Аг2, М) + + ( — 1)' ~вК(А! в,М)) = (!пХ+ у — Н, о)/!и М+ 1/2— (бо(Аг — 1) + А (Х вЂ” 2)/1 + + 6, ~(!У вЂ” в)/(в — 1)) + О(!У '); (с) Х '(!У + (1 — М ') х Еь=>(-Ц (г)К(Н ",М)) =1+ э(1 — М 'П(в — 1)/ЬоМ+б Р'-2)+" +6.-~Р'-в))+ 0Р-'), 21. Пусть всего имеется Ал узлов.
т1исло непустых ссылок равно Аи — 1, а количество узлов без ссылок — Х, так что общее количество пустых ссылок составляет МАн— Ак + 1 — Х. Для получения среднего количества пустых ссылок в любом фиксированном узле следует разделить найденное значение на М. [Среднее значение Ак приведено в упр. 20, (а).] 22. Для каждой из М последовательностей лидирующих битов имеется такой узел, что, по меньшей мере, два ключа начннаются с этой погледовательности.
Вероятность того, что с нее начинается ровно а ключей, составляет ( )М-"(1 — М-')™, так что среднее количество узлов луча на уровне ! равно ЛХ'(1 — (1-М ') ) — Н(1-М )' 23. Рассмотрим более обшую задачу — случай для произвольного в (как в упр. 20). Если на уровне ( имеется а~ узлов, то е них содержится аьы ссылок н Ма~ — аоы позиций, в которых поиск может быть неудачным. Таким образом, среднее количество проверок цифр составляет 2, е(1+ 1)М ' '(Ма~ — аоы) = ~, „М 'аь Используя формулу для ав в случайном луче, получаем К(!»'+1, 1, М) — 2К(Я+1, 2, М) + + (-1)'(в+1) К(Аг+1, в+1, М) Аг+ 1 !и!У+ 7 — Н, 1 бг(Аà — 1) 5,(7У-в) !пМ 2 1 в 24.
Необходимо найти решения рекуррентных соотношений хе = хг = уе = ув = О, х.=т= ~;- ( " )(х.,+...+х. + ~; (ну~О)) 1-~-" е 1<1< =а +т "~ ~( )хв, у„=т ~ ~( ) (у, +. +у + ~~~ (п,эвО)пв) 1+ е» 1«в< =6»+ '-"Я"„)ув, для и > 2, где а = т(1 — (1 — 1/т)") и 6» = -'(т — 1)п(1 — (1 — 1/т)" ').
Согласно упр. 17 н 18 ответы таковы: (а) хл = Ж+ 1'и — (/и — (Х = 1) = Ал + Х вЂ” 1 (этот результат может быть получен непосредственно, поскольку количество узлов в лесу всегда на Х вЂ” 1 больше количества Узлов в соответствУющем лУче!); (Ь) Ул/Х = 1в(М вЂ” 1)1~и/Аг = ~~(М— 1)((!пХ+ 7)/!пМ вЂ” 1 — 5~(Х вЂ” 1))+0(Х '). 25.
(а) Пусть Ан = М(Ж вЂ” 1)/(М вЂ” 1) — Ел; тогда при Аг > 2 имеем (1 — М' л)Ел = М— 1 — М(1 — 1/М)ь '+М' 2 < (~)(М вЂ” 1)н «Е». Поскольку М вЂ” 1 > М(1 — 1/М)л по индукции находим, что Ел > 0 (Ь) По теореме 1.2.7А при х = 1/(М вЂ” 1) и и = Ж вЂ” 1 находим /ул = ал+М ~ и 2 в („) (М вЂ” 1)™0ь, где а~ = О и 0 < аь < М(1-1/М) л/!а М < (М вЂ” 1) ~/М !и М при Х > 2. Следовательно, 0 < 17л < (М вЂ” 1) Ал/М !и М < (М вЂ” 1)()!7— 1)/!и М. 26. Приняв д = -', в = --' во втором тождестве упр. 5.1.1-16, получим 1/3-1/(3 7)+ 1/(3.
7 15) †.. = 0.28879;несколько удобнее использовать в = — 1 н взятьполовину полученного результата. Можно также применить формулу Эйлера из упр. 5.1.1-14, включающую только отрицательные степени двойки. (Джон Ренч (ЛоЬп %гепсЬ) вычислил это значение с точностью до 40 десятичных цифр: О. 28878 80950 86602 42127 88997 21929 23078 00889+.) 27. (Рапи собственного удовольствия доведел» точность решения до 0(А! ').) В обозначенинх из упр. 5.2.2-38 и 5.2.2 — 48 имеем „„,,Е„„,(2' ") (1-2 ) Сч = ЙЪ+ Х вЂ” 1+ — пА! — б+ ~ (-1)" 2 где а = 2/(1 1) — 4/(3 3 1) +8/(7 7 3 1) — 16/(15 15.
7 3 1) +. 1. 60669 51524 15291 763 78 33015 23190 92458 04806-, а/) = 2/(1 3 1) — 4/(3 7 3 1)+ 8/(7. 15 7 3 1) — - 0.60670. Эти численные оценки приводят к выводу, что а = )7+ 1, т, е. к факту, который нетрудно доказать. Значение (2' ") (1 — 2 ) раино 0(Х' ") согласна упр, 5.2.2-46; а Ул+»/(Х+1) = Пи+| — (7ж >о Следовательно, С|г = »(л» | — (а — 1)Х вЂ” а+0(Х ') = (Х+ 1) 16(Х+ 1) + Х((7 — 1)(!п2+ » — а+ б |(Х)) + -' — 1/!п4 — а — -'б|(Х) -»- 0(Х ') согласно упр 5 2.2-50. Отклонение длины внутреннего пути дерева цифрового поиска было вычислено в работе К|гзсЬепЬо(ег, Ргой!пйег, апй Бкрапйоизй1, Я(СОМР 23 (1994), 598-616.
28. Выкладки в тексте и упр. 27 применимы для любого М > 2 — следует только подставить М вместо 2 в соответствующих, вполне очевидных местах. Следовательно, среднее количество проверок цифр при случайнол» успешном поиске составляет Сгг(Х = (!к+» -ам+1+0(Х ') = !ойм Х+ (7 — 1)/!пМ+-' — ам+б |(Х)+(!ойм Х)/Х+0(Х '); при неудачном поиске оно равно Сл+| — Сн = Улэ»/(Х -|- 2) — ам + 1 + 0(Х ') 1ойл, Х+ 7/!пМ+ -' — ам — бо(Х+ 1) + 0(Х '). Здесь б,(п) определена в упр. 19, а ам = ~'(-1)'М'а'/(М'ь' — 1)'(М' — 1)... (М вЂ” 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
