Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 24
Текст из файла (страница 24)
Таким образом, г пт = г ™ тогда и только тогда, когда г' имеет ие более одного узла. 13. Если Гл естественным образом соответствует бинарному дереву В', корнем В' является корень крайнего справа дерева Е. Левая связь узла х в В' представляет собой связь с крайним слева потомком х в г'~, который является крайним справа потомком х в Е; аналогично: правая связь представляет собой связь с левым братом в Г. Нрммечамие: поскгшьку В естественным путем соответствует Глт, ответ к упражпеиию 13 гласит, что 1поп1ег(В) = роегогг(ег (г'лт) = ровгоп1ег (г'~) = ргеоп1ег (г') .
16. Лес г ~ С получается путем размещения деревьев г' под первым в обратном порядке обхода узлом С. Ассоциативиость этого оператора доказывается следующим образом: Г ~ (С)Н) = (Н~С гг) = (г !С) ~ Н. Заметим, кстати, что ровсоп1ег (Е ~ С) = ровсогггег (Р) роэгоп(ег (С) и что г' ~ (СН) = (г ( С) Н, если С— непустой лес. 17, Любой непустой лес можно записать как Г = (С ~ ) Н, где означает одно- узловой лес; тогда г'~ = Н (Сл ~ ) и г'т = (Нт ~ ) С~. В частиости, равенство г и = г т невозможно, если только Н пе является пустым лесом Л, поскольку первое дерево НЯ ие может быть Нт ~ ", С также должно быть Л.
Кроме того, Г = Гт тогда и только тогда, когда С = Н~. В этом случае невозможно также выполиеиие г и = Глт, если только ие выполняется условие С = Л; в противном случае первое дерево Стл должно иметь больше узлов, чем само дерево С. Похоже иа то, что условие г'~ = Г~~ яе выполияется, если только ие выполияется условие Г = г'и.
При этом предположении г'Ят = г'™ тогда и только тогда, когда и Е и г т являются самосопряжеииыми. Дэвид Каллаи (Ват1г( Сайки) открыл два бесконечных семейства таких лесов с параметрами г, у, )г > О. енапомким, что ргеогбег — ирямой порядок обхода, роегогбег — обратима иорядок, а ктогйм— симметричямй порядок обхода. — гГргкмеч. яер. сделано для ьрьрж!я(апаса,ого 102 ОТВЕТЫ К УПРАЖНЕНИЯМ у 1 (В этих примерах 1 = 2, у = 3 и Й = 5.) Существуют ли другие возможности? 18. Всего имеется Сш = 9694843 лесов, разбитых на 20982 класса. Наибольший класс представляет собой цикл длиной 58968, одним из элементов которого является (( О ( 0) ) О ) О ((0 ( 0) О ) О ) О. Самыми короткими являются шесть двухэлементных классов (в соответствии с упражнением 17), состоящих из строк 000000000000000, ООООИООООО))0000, ОООИШОООО)))))000, ООИ(ШИООО))))))))00, ОИОО)ИОИ))0))И)0))0, ОШИИ(ШОО))))Э))))))0 и их транспозиций.
Строки И И И ( О ) ) ) ) ) ) ) О О О О 0 0 О, О О 0 О О О О И И И ( О ) ) ) ) ) ) ) и ИИИ(00000000))))))) имеют клинообразные бинарные деревья и образуют единый класс размером 3. Путь, проходшций от О И 0 И) О ) ) ( О ) И О 0) 0) ) О до И О О ) И) 0) (О) (О 0) (О О) ), содержит 3 120 элементов, одним из которых является (2). В соответствии с гипотезой из ответа к упражнению 19, кратчайший возможный цикл имеет длину 6; при и = 15 имеется 66 таких циклов. (Следующий в порядке возрастания размера цикл имеет длину 10 и включает элемент 0(0 О О) 0 ИИО) О)) ИО))); цикл с такой длиной только один.) 19.
Преобразование Г в Г.+1 в алгоритме Р можно перефразировать следующим образом: "найти последний узел в прямом порядке обхода, скажем, х, который имеет левого брата, скажем, у. Удалить х из его семейства и сделать его новым крайним справа дочерним узлом у. И если х < п, заменить всех потомков х (х + 1,...,и) тривиальными одноузловыми деревьямп". Таким образом, преобразование Гзл в Гл+, можно описать следующим образом, если вспомнкть, что Й-й узел Г в прямом порядке обхода представляет собой Й-й с конца узел ГД в обратном порядке обхода: "найти первый узел в прямом порядке обхода, скажем, х, у которого есть правый брат, скажем, у.
Удалить х из его семейства и сделать его новым крайним слева дочерним узлом у. И если х < и, заменить всех потомков х (х + 1,..., и) тривиальными одноузловыми деревьями". Аналогично можно перефразировать преобразование С в С +ы выполняемое алгоритмом В: "найти у, корень крайнего слева нетривиального дерева; затем найти Й, его крайний справа дочерний узел. Удалить Й и его потомков из семейства ) и вставить их между у и правым братом .у.
Наконец, если у > 1, сделать ) и его братьев дочерними по отношению к,у — 1, а,у — 1 — дочерним узлом у — 2 и т.д.". сделано для эуэлкпИапаса.ого Отнеты к упРАжнениям 103 Когда это преобразование изменяет представление с левым братом н правым сыном с Сдг на С'~Д (см.
упражнение 16), оно оказывается идентичным преобразованию Х"' в Ь'"+, в представлении с левым сыном н правым братом. Следовательно, Сйэ = Гл, поскольку при у' = 1 выполнение этого тождества очевидно. (Отсюда вытекжт, что последовательность таблиц е1... е„1 для бинарных деревьев, сгенерированная алгоритмом В, представляет собой последовательность таблиц 4, 1 ...4 для строк скобок, сгенерированную алгоритмом Р; это явление продемонстрировано в табл.
1 и 2.) Лес г Я™ называется дуэльным лесу Г; см. упражнение 26 (ф). Ряд симметрий списков лесов был изучен М.Ч. Эрой (М.С. Ег) ]Сошр. Х, 32 (1989), 76-83]. 20. (а) Это утверждение, обобщающее лемму 2.3.1Р, легко доказать по индукции.
(Ъ) Приведенная ниже процедура практически идентична алгоритму Р. Т1. [Иййцнэлйзацйя.] Установйть Ьэь э < — 3 й Ьэь 1 < — Ьэь ~ 0 для 1 <» Й » <и; установить также Ье - Ьн — 0 и т — Ь7 — 3, где 7э' = Зп + 1, Т2. [Посещение.] Посетить последовательность 61... Ьн. (Сейчас 6 = 3 и Ь +~ .. ...Ьл = 0...О.) ТЗ. [Простой случай?] Установить Ь вЂ” О. Если Ь ~ = О, установить Ь, — 3, т — т — 1 и перейти к шагу Т2. Т4. [Поиск Я Установить 1 - гп — 1 и Ь вЂ” )э' — 3. Пока Ь, = 3, устанавливать Ьз» вЂ” 0,6» "З,,у э — 1ий — Ь вЂ” 3. Тб. [Увеличение Ь;.] Завершить работу алгоритма, если,у = О. В противном случае установить 6„- 3, гп +- М вЂ” 3 и вернуться к шагу Т2.
1 [См. Я. ЕэЬл, ТЬеогенса1 Сотр. Ясь, 10 (1980), 63 — 82, В этой статье Закс уквзывжт, что еще проще сгенерировать последовательность х1... х„индексов 1, таких, что Ь, = 3, с использованием алгоритма, практически идентичного алгоритму из ответа к упражнению 2, поскольку комбинация х1... э„для корректного тернарного дерева характеризуется неравенствами хь 1 < хь < ЗЙ вЂ” 2.] 21.
Для решения этой задачи можно по сути скомбинировать алгоритмы Р и 7.2.1.21 . Дэя удобства будем считать, что п1 > 0 и п1 + ". + пс > 1. С1. [Инициализация.] Установить 1 — Ф. Затем для у = 1,..., 2, 1 (в указанном порядке) выполнить пу раз следующие операции: установить 6| — 1, 6| +1 - 6| 1 — 0 н 1 - 1 — у.
Наконец, установить Ьэ — Ьн — сэ — 0 ит -М вЂ” г. С2. [Посещение.] Посетить Ь1 ... Ьн. (В этот момент 6,„> 0 и Ь,„+1 = ° = Ьн = 0.) Сз. [Простой случай7] Если Ь ! = О, установить Ь 1 — 6, Ь - О, т - гп — 1 и вернуться к шагу 02. С4. [Поиск э'.] Установить с1 - Ь, Ь - О, 1 - т — 1 и Ь вЂ” 1. Пока 6; > сь, устанавливать Ь вЂ” Ь + 1, сь — 6, Ь; — О и у —,у — 1. сделано для мгэкэкЛя$ааа1а.ого 104 ОТВЕТЫ К УПРАЖНЕНИЯМ 7.2.1 сэб. [Увеличеиие Ь .] Если Ьз > О, найти наименьшее 1 > 1, такое, что Ь < сп и выполнить обмен Ьу сь Иначе если у > О, устаиовить Ьз ~- с1 и с1 — О. В противиом случае завершить работу алгоритма.
СО. [Обращеиие и рвзвертываиие.] Устаиовить у — й и 1 — Х. Пока с > О, устаиавливать Ь| „— с„1 ~- 1 — сз и,у ~- у — 1. Затем устаиовить т ~- Х вЂ” сь и вериуться к шагу 02. 1 В этом алгоритме предполагается, что Ж > п| + 2пэ + ° ° ° + спь [См. ЗЕСОМР, 8 (1979), 73-8Ц 22, Вначале заметим, что значение 41 может увеличиваться тогда и только тогда, когда в связанном представлеиии г1 = О. В противном случае следующий за 41...4„1 элемеит получается путем поиска наименьшего у, такого, что 4» > О, и установкой ду — О, 4 +1 - 41+~ + 1. Можно также считать, что а > 2. К1.
[Ииицивлизация.] Устаиовить (ь +- Ь + 1 и гь +- 0 для 1 < х < и; установить также 1„- г„О. К2. [Посещеяие.] Посетить бинарное дерево, представленное связями 111з...1„ и г1гэ ..г„. К3. [Простые случаи7] Устаиовить у +- гь Если у = О, установить г1 — 2, 11 - 0 и вернуться к шагу К2. Ииаче если 11 = О, установить 1, - 2, г1 — гэ, гз — 1э, 1з - 0 и вернуться к шагу К2. В противном случае установить у — 2 и й +- 1. К4. [Поиск у и Ь.] Если г, > О, установить й - у и у 1- гз.
Затем, если у 11 у — 1, установить у — у + 1 и повторить данный шаг. Кб. [Перетасовка поддеревьев.) Установить 11 - р„гз г„, г„— 1„и 1э ~ — О. Если у' = й, перейти к шагу К2. К6. [Сдвиг поддеревьев.) Завершить работу алгоритма, если р = и. В противном случае, пока й > 1, устанавливать й+- Ь вЂ” 1, у - у — 1 и гз — гы Затем, пока ,у > 1, устаиавливать.у - у — 1 и г; — О. Вернуться к шагу К2. 1 (См. аиализ алгоритма в упражнении 45.
Корш [Сошр. Х, 48 (2005), 488-497; 49 (2006), 351-357] показал, что данный алгоритм можно расширить для Ф-арных деревьев, а также нашел зффективиое обобщение алгоритма В для 1-ариых деревьев.) 23, (а) Поскольку переменная х„иачииается с 2п — 1 и проходит назад и вперед С„1 рвз, в конце ее значение оказывается равным 2а — 1 — (С„1 шоб 2) при и > 1. Кроме того, последнее значение хз представляет собой константу при всех и > у. Таким образом, последняя строка с1хэ... имеет вид 1 2 5 6 9 11 13 14 17 19 и содержит все нечетные числа, меиьшие 2п, за исключением 3, 7, 15, 31, ... (Ъ) Аивлогичио: перестаиовка в прямом порядке обхода, характеризующая последиее дерево, представляет собой 2" 2" ' ...
1 3 5 6 7 9 10 где й = [18 и]. В лесу узел 21 является родительским по отношению к 21 ' узлам (21 ',21 1+1,...,21 — 1], 1 < у < Й, адеревья (2 +1,...,п) тривиальны. Прммечанпе: если алгоритм Х после его окончания перезапустить с шага Х2, ои сгеиерирует ту же последовательиость, ио в обратном порядке.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
