Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 27
Текст из файла (страница 27)
Путем очевидных поправок к шагам Т1-Т5 можно обобщить результат для произвольных (-арных деревьев. Пусть ф— количество (-арных деревьев с и внутрен- (О ними узлами; таким образом, С„= С~~ ) и С(с) = ((Ф вЂ” 1) и+ 1) ' (~„"). Если между посещениями изменяется 6 степеней 5;, то Ь > х в С„случаях. Так что простой (О случай осуществляется с вероятностью 1 — С('))/СР ш 1 — (г — 1)~ ~/(и, и среднее количество установок 51 — 0 на шаге Т4 составляет (С„) + .
+ С, ~/С„ (~) О) 1 (О (1 — 1) /((и — (( — 1) ), нли 4/23 при ( = 3. Можно также изучить (-арную рекурсивную структуру Агт — — ОА,), (А (О (О (() где О < ($ — 1)р < 9, обобщающую (5). Количество таких последовательностей степеней, С)ч, удовлетворяет рекуррентному соотношению (21) с тем исключением, что (О С(') = 0 прн р < 0 или (Ф вЂ” 1) р > (). Общее решение имеет вид С(0 9-((-1)р+1 р+9 р+9 ( 1 р+9 и С,1 — — С„(0,)„). Треугольник для ( = 3 начинается следующим образом: (О (О 1 1 1 1 2 1 3 3 1 4 7 1 5 12 12 1 6 18 30 1 7 25 55 55 1 8 33 88 143 сделано для ыг(иьк$н(ана1а.ого 112 ОТВЕТЫ К УПРАЖНЕНИЯМ 32. Базовое лексикографнческое рекуррентное соотношение для всех таких лесов имеет вид .4(по пь пт) = ОА(по 1 пь ° ° ° пт) 1.4 (по1пт 11 ° ° ~ пт) 1 ° 11А (™о~ пь ° ° ° ~ пт 1) ~ где по > пз+2пз+ +(1-1)пт и пь..., пт «О; в противном случае А(по,аь..., пт)— пустая последовательность, за исюпочением последовательности А(О,...,0) = е, состоящей из одной пустой строки.
Шаг 61 вычисляет первый злемент А (по„, ит). Мы хотим проанализировать пять величии: С вЂ” количество выполнений шага 62 (общее количество лесов); Š— количество переходов от шага 63 к шагу 62 (количество простых случаев); К вЂ” количество перемещений Ьз в список с на шатт 64; Š— количество сравнений Ь. с некоторым с; иа шаге 63; Š— количество установок ст ~- 0 на шаге 65. Тогда присваивание Ьт,, — су в цикле на шаге 66 выполняется К вЂ” Е- пт — — пт раз.
Пусть а — вектор (по, пь..., и„), и пусть е — единичный вектор с 1 в позиции т1 Пусть |п~ =по+от+ .+и, и ЦпЦ = пт+2пз+ +тат. Используязти обозначения, мы можем переписать приведенное выше базовое рекуррентное соотношение в более удобном виде: А(п) = ОА(п — со),1А(п — ст),...,ФА(п — ет) при ~а! > ЦпЦ. Рассмотрим общее рекуррентное соотношение т Г(п) =)'(и)+ ~у Г(п — еу) ()и! > ЦнЦ), у=о где Г (и) = О, если вектор и имеет отрицательный компонент.
Если 1 (и) = ()п~ = ОЦ то Р (и) = С (и) — общее количество лесов. Согласно ответу к упражиенито 2.3,4.4- 32 С(п) = ' ~ ) = ~~~ '(1 — т') Г тто'пь ' " ' пт', отто~. 1ттт-ь от 1~ пт+ь ~пт ! ) ! что является обобщением формулы Стч из упражнения 26 (которая представляет (тт собой случай по = (1 — 1) о+ 1 и и, = р).
Аналогично: при выборе друптх функций ядра 1 (и) мы получаем рекуррентные соотношения для остальных величин Е (а), К(п), Х (и) н Е (и), необходимые для нашего анализа: Х(п) = ЦтЦ = по+ 1 и по > Цп$Ц дает Р(п) = Е(п); 1 (и) = Цп~ > во) дает Р (и) = Е (тт) + К (и); йн) = Цп1 =! пЦ + Ч дает Р(п) =С(п)+К(п) — Е(п); У (и) = ~,,~1<ест пу (пь > О) дает г' (и) = Е (и) . сделано для ьуоуьнлн(апаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 113 Символьные методы из упражнения 2.3.4.4-32, похоже, не в состоянии привести к быстрому решению этих более общих рекуррентных соотношений, но можно легко установить значение С вЂ” Е, заметив, что на шаге 02 Ь + т < Аг тогда и только тогда, когда предыдущим шагом был 03; следовательно, С(в) — Е(п) =~ С(в — Д), где г) =ез — Π— 1)ео, эта сумма перечисляет все подлеса, в которых пг + " . + в, -- количество внутренних узлов (не являющихся листьями) — уменыпено на 1.
Аналогично можно обозначить через С'*'(и) =~ (С(в-а~У1 —" -гсЛ) $чг+" +1г =х) количество подлесов, имеющих в1 + ° + вс — х внутренних узлов. Тогда мы имеем 60 К(в) — г(в) = Есро(в). Эта формула аналогична (20), поскольку 6 — [6 = О) > х > 1 на шаге 05 тогда и только тогда, когда 6, > 0 и Ь,+ ~ > " > Ь„,. Такие строки степеней в прямом порядке обхода взаимно однозначно соответствуют лесам из Сбо (в), если удалить из строки 61... Ьн подстроку 6 ч+1... 6 и соответствующее количество завершающих нулей, Из этих формул можно заключить, что алгоритм Заков-Ричардса прн в1 = из + + .
+ и, + О (1) требует только О (Ц операций на одно посещение дерева, поскольку С(п — Д)/С(в) = нуво /(~п~ — 1)6» (1~4+0(~и~ ) прн,~ > 1. Действительно, значение К достаточно мало почти во всех случаях, представляющих практический интерес. Однако алгоритм может оказаться медленным при больших значениях пь Например, если 1 = 1, по = гв+с+ 1 и в1 = т, алгоритм, по сути, вычисляет все г-сочетания т+г элементов; тогда С(в) = ( ~) и К(в) — х(в) = (,+") = й(тС(п)) при фиксированном г. (Для обеспечения эффективности во всех случаях можно отслеживать завершакппне единицы; см. Впзкеу аш1 Вое!апсв чап Вагопайпеп, Сопйтеээпз АГшпегалншп, 41 (1984), 53-02.) Точные формулы для К, Е и (в особенности) 1,, похоже, слишком сложны, но эти величины можно вычислить следующим образом.
Назовем "активным блоком" леса крайнюю справа подстроку ненулевых степеней; например, активным блоком 302102021230000000 является 2123. Все перестановки активного блока встречаотся одинаково часто. Действительно, обозначим через О (в) сумму величин '"Завершающие нули(13) — Г, взятую по всем строкам степеней в прямом порядке обхода 11 для лесов, определяемых в. Тогда блок с в.
вхождениями у (1 < у < г) является активным ровно в;Р (в — гг1 )1 — ° — вуг) + (п( + + в', = в1+ ° - + в~) случаях. Например, можно в трех местах вставить 21230000 в заданную строку 3021020000 для получения леса с активным блоком 2123. Вклады в К и Ь при выравнивании активного блока влево (когда перед ннм нет ни одного нули) могут быть вычислены сделано для ьггнгок! н$апаса.ого 7.2.1 114 ОТВЕТЫ К УПРАЖНЕНИЯМ квк в упражнении 7.2.1.2-6, а именно: к( ) = ю(е„, (х)...
е„, ( )) „ 1(п) = ю е„, (х)...е„, (а) ~~) (и; — хг((х))гу(х) 1<ьсук~ с использованием обозначений из упомянутого упражнения. Аналогичные вклады получаются и в общем случае; следовательно, К(п) = к(н)+ ~~~ О(п-и') л(п'), Ь(п) =1(п) + ~ О(п — и')1(п'), Е( ) =~О( — '), где суммироввнне выполняется по всем векторам и', таким, что и' < и для 1 < у < <Ь н ~н'~ — '5Щ = ~п~-(~н5 ни)+ +н', < нг+ +н,— 2. Остается определить |2(п).
Пусть С (л;,у) ознвчвег количество лесов со спецификацией и = (по,..., п~), в которых последний внутренний узел в прямом порядке обхода имеет степень у. Тогда С(п) =~ С(п;у)и С(п+ен1) =С(п+ез,2) =" = С(я+е~,с) =С(п)+О(п). Нз втой бесконечной системы линейных уравнений можно вывести, что С (и) + В (и) рзвно в~ ю ~~) ... у (-1)"+"'+ь (',' ', ~1С(п+(1+ге+ +н)е1 — 1з,6 — — 1~~д). и=О я=о хм.~с / Разумеется, хотелось бы получить более простое выражение, если, конечно, оно существует.
38. Очевидно, что швг Ь1 выполняет 4п+ 2 обращений к памяти. Швг ЬЗ переходит к шагам Ь4 или Ь5 С вЂ” С. 1 рвз для конкретного значения у; следовательно, его стоимость составляет 2С„+З~Х~ (и — у)(С- — С, ) =2С„+З(С„+ "+С~+СЕ) обрвщений к памяти.
Швги Ь4 и Ь5 имеют суммарную стоимость 6С„-6 обращений к памяти. Таким образом, весь процесс требует 9+ О (и ~~~) обращений к памяти нв одно посещение. 39. Диаграмма 1Оигв формы (р,4) и записи 96 соответствуют элементу А,„, который имеют левые скобки в позициях р+ 4 — 1 — реп ..., р + д + 1 — рзр, н правые скобки в позицивх Р+ д + 1 — Рм, ..., Р+ 4+ 1 — Р1ч. Длины Уголков Равны (4+ 1,4,...,1„р,р-1,..., Ц'1(4-р+ 1)„твк что Сг, = (р+ д)!(д- р+ Ц/ ~(р((4 + 1))) согласно теореме 5.1.4Н. сделано для тимлилн$ана4а.ого 7.2.1 отвкты к упрлжнкниям п3 40.
(а) С = (~~с) — ("+с!) ьэ (с+с) + ("+с1) = ("+с+') (п1обп1о2); теперь воспользуйтесь упражнением 1.2.6-11. (Ь) Из 7.1.3-(36) мы знаем, что м(п й (и+ 1)) = = с(п+ 1) — 1. 41. Она равна С (1сз)/(1 — зС (ии)) = 1/ (1 — з — ииС (1сз)) = (1 — !сС (ии))/ /(1 — в — з), где С(з) — производящая функция для чисел Каталана (18). Легко видеть, что первая из этих формул, С (!их) + сС (!сх) + гзС (ии) + ° °, эквивалентна (24). [См. Р.А.
МасМаЬоп, СошЬ!наготу Апа)уз!э, 1 (СвшЬгЫйе Пшю Ргезэ, 1916), 128-130.[ 42. (а) Элеме1пы а!... а„определяют полностью самосопряженную строку вложенных скобок а!... аз, причем имеется Се<„»1 вариантов а1... а„с е правыми скобками. Таким образом, окончательный ответ: (Ь) Ровно С<„!)~з [и иечетно[, поскольку самотранспонированное бинарное дерево определяется своим левым поддеревом. Пункт (с) имеет тот же ответ, поскольку лес Г явлжтся самодуальным тогда и только тогда, когда лес г л — самотранспонированный. 43.
По индукции по д — р получаем Я Р с„=с,-('; ')с ' =1;!-с (' '-")с,, с 0 44. Количество обращений к памяти между посещениями составляет Зу — 2 на шаге ВЗ, А + 1 на шаге В4 н 4 на шаге Вб, где А — количество присваиваний р — г„.
Количество бинарных деревьев, у которых 11 > х, для заданных ! и х равно [с» У * '1 С(з) при 1 < и, поскольку такие деревья получаются путем присоединения я+3 поддеревьев ниже у + х + 1 внутренних узлов. Присваивая х = 0 и используя формулу (24) и упражнение 43, мы находим„что данное значение ! встречаетсяС1» 1 0(„1+1) = С„+! 1 — С» !раз. Таким образом, 2",у повсембинарнымдеРевьЯмРавняя+~ .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
