Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 11
Текст из файла (страница 11)
Ь) Вспомним из упражнения 2.3.4.5-0: расширенное гпернарное дерево характеризуется тем свойством, что каждый его узел имеет степень либо О, либо 3; расширенное тернарное дерево с п внутренними узлами имеет 2в+ 1 внешних узлов, т.е. всего Ф = Зп+ 1 узлов. Разработайте алгоритм для генерации всех тернарных деревьев с и внутренними узлами путем генерации соответствующих последовательностей 6|6»... 6»г в лексикографическом порядке.
сделано для мчи»дп[апаса.ого 48 КОМБИНАТОРНЫЙ ПОИСК ° 21. [36[ (С. Закс (Я. Еайз) и Д. Ричарде (П. Н)с)тагдв), 1979.) Продолжая выполнение упражнения 20, поясните, как сгенерировать последовательности степеней в прямом порядке обхода для всех лесов с М = по + ° + кч узлами, среди которых степень у имеют ровно яз узлов. Пример: при 1 = 3, по = 4 и п1 = пз = пз = 1 корректными последовательностями Ь1бзбзб4бзбебт являются 1203000, 1230000, 1300200, 1302000, 1320000, 2013000, 2030010, 2030100, 2031000, 2103000, 2130000, 2300010, 2300100, 2301000, 2310000, 3001200, 3002010, 3002100, 3010200, 3012000, 3020010, 3020100, 3021000, 3100200, 3102000, 3120000, 3200010, 3200100, 3201000, 3210000.
~ь 22. [36[ (Д. Корш (Л. КогзЬ), 2004.) В качестве альтернативы алгоритму В покажите, что бинарные деревья могут быть также эффективно сгенерированы непосредственно в связном виде, если генерировать их в сслексяом порядке чисел 61... 4, определенных в (9). (Реальные значения А... 4, 1 ие должны вычисляться явно; должна выполняться работа са связями 11... 1„и т1...г„таким образом, чтобы получались бинарные деревья, соответствующие значениям 616з...
Ы„л, равным 000... О, 100... О, 010... О, 110... О, 020... О, 001... О, ..., 000... (п — 1).) м 23, [35[ а) Какова последняя строка, посещаемая алгоритмом Х7 Ь) Каково последнее бинарное дерево, посещаемое алгоритмом 17 Умзание: см. упражнение 40. 24. [32[ Какие последовательности 1р11... 1ш, г1...
гш, й1 йиь й1 .. Чш и и1... иы соответствуют бинарному дереву (4) и лесу (2) при использовании обозначений из табл. 37 ь 23. [ЮО[ (06резка и прививка.) Представляя бинарные деревья способом, использующимся в алгоритме В, разработайте алгоритм, который посещает все таблицы связей 11 ... 1„и г1... г„таким образом, что между визитами только одна связь изменяется с у на 0 и одна — с 0 на у для некоторого индекса у. (Другими словами, каждый шаг удаляет некоторое поддерево у из бинарного дерева и помещает его и другое место, сохраняя прямой порядок обхода.) 26.
[Ш1[ (Решешка Крееераса.) Пусть Г и Г' — и-узловые леса, узлы которых пронумерованы от 1 до и в прямом порядке обхода. Мы записываем Г< Г' ("Г срастается с Гы), если из того, что у и й являются братьями в Г', вытекает, что они братья и в Г; 1 < у < й < и. На рис.
39 приведено такое частичное упорядочение для случая и = 4; каждый лес кодируется последовательностью с1 ...с„из (9) и (10), которая указывает глубину каждого узла. (При таком кодировании у и й являются братьями тогда и только тогда, когда су = сь < сзеы..., сь-м) а) Пусть П вЂ” разбиение (1,..., п). Покажите, что существует лес Г с узлами, помеченными (1,..., п) в прямом порядке обхода, такой, что у' = й (шодп1о П) сь.у брат й в Г сделано для ивлк!н$ана1а,ого 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОВ'1зЕКТОВ 49 Рмс. 39. Решетка Кревераса четвертого порядка. Каждый лес представлен последовательностью глубин узлов с~ сзсзс4 в прямом порядке обхода (см.
упражнения 28-28) тогда и только тогда, когда П обладает свойством ненерссскосмостп (попсгоевшб): из 4 < у < к < 1 и из 1 ш к и у ш 1(шос(п!о П) вытекает 1 ш у ш к ш 1(шос(п1о П). Ь) Поясните, как длн двух заданных и-узловых лесов Р и Р' вычислить их наименьшую верхнюю границу Рк'Р', которая представляет собой элемент, такой, что Р< С и Р'< С тогда и только тогда, когда Р'кГ'< С.
с) Когда Р' покрывает Р по отношению к к (см. упражнение 7.2.1.4 55)? Й) Покажите, что если Р' покрывает Р, то он меньше Р ровно на один лист. е) Сколько лесов покрывают Р так, что узел и имеет еь дочерних узлов (1 < к < и)? 1) Какой лес является дувльиым по отношению к лесу (2) при использовании опре- деления,вуальности из упражнения 19? к) Докажите, Р<Р' и „Р' Р . (И- за этого свойства дувльные элементы располвгаютсв симметрично относительно центра рис. 39,) Ь) Объясните, квк длв двух заданных и-узловых лесов Р и Р' вычислить их наибольшую нижнюю границу РдР', те, элемент, такой, что С< Р н Ск Р' тогда и только тогда, когда Ск Р д Г'. 1) Удовлетворяет ли эта решетка полумодулириому закону, аналогичному закону из упражнения 7.2.1.8-12 (1)? ~ 27. 1МУУ) (Репмгнка 2)амари.) Продолжая выполнение упражнения 26, запишем Р -~ Р', если,у-й узел в прямом порядке обхода длн всех у имеет, квк минимум, столько же потомков в Ре, как и в Р.
Другими словами, если Р и Е' характеризуются своими последовательностями л1... л„и а',... а'„(см. табл. 2), то Р -~ Г' тогда и только тогда, когда л < а'; при 1 < у < и (рис. 40). сделано для мгиьклп$апаса.огя 56 КОМБИНАТОРНЫЙ ПОИСК 7.2д 2ПО Опз О10 1!2 0200 1010 010 Рис. 40.
Решетка Тамарн четвертого порядка. Каждый лес представлен: а — последователыюстью глубин узлов; Ь вЂ” количеством потомков в прямом порядке обхода (см. упражнения 26-28) в) Покажите, что координаты пнп (вт, втт) пнп (вз, в~в)... ппп (в„, в'„) определяют лес, который является наибольшей нижней грвницей Г и Г' (обозначим ее квк ГЛ.Г'). Указание: докажите, что вт... в„соответствует лесу тогда и только тогда, когда нз 0 < й < в; вытекает в +в + к < в;, для О < т' < и, если положить во = и. Ь) Когда при таком частичном упорядочении Г' покрывает Г? с) Докажите, что Г -1 Г' тогда и только тогда, когда Г"з -1 Гтт. (Сравните с упраж- нением 26 (к).) т1) Поясните, как вычислить наименьшую верхнюю границу ГТГ' для данных Г н Г'.
е) Докажите, что из Г < Г' в решетке Креверасв вытекает Г -т Г' в решетке Тамврн. 7) Истинно или ложно: ГдГ' -1 ГЛ.Г'? к) Истинно или ложно: ГЯ Г'1< ГТГ'? Ь) Каковы длиннейший и кратчайший пути от верха решетки Твмври до ее низа, такие, что нв пути каждый предшествующий лес покрывает последующий? (Такие пути называются максимальными цетючками решетки; сравните с упражнением 7.2.1.4-55 (Ь).) 26. (Мйб) (Решетпка Стпепли.) Продолжая упражнения 26 и 27, определим еще одно частичное упорядочение нв и-узловых деревьях, говоря, что Г С Г', если координаты глубины от...С И С~1...С„' уДОВлетвОряютсООтношениям с < с' при 1 < т' < и (рнс.
41). в) Докажите„что зто частичное упорядочение представляет собой решетку, пояснив, каким образом вычислить наибольшую нижннно границу Г П Г' н наименьшую верхнюю границу Г О Г' любых двух заданных лесов, сделано для ьтттдтжЛп?анаСа.ого 7.2,1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБ'ЬЕКТОВ 51 Рис. 41. Решетка Стекли четвертого порядка, Каждый лес представлеи последовательиостью глубин узлов в прямом порядке ейссда (см. упражиеиия 26-23) Ь) Покажите, что решетка Стенли удовлетворяет дистрибутивным законам Гг1(СОН) =(РОС)0(РАН), РО(СОН) = (РОС) О(ГОН).
с) Когда в данной решетке Р' покрывает Р? 6) Истинно или ложно утверждевие: Р С С тогда и только тогда, когда г и С С"? е) Докажите, что Г С Р' в решетке Стенли, когда Р -1 Р' в решетке Тамари. 39. [НМ81] Покрывающий граф для решетки Тамари иногда называют "ассоцив эдром" (аввосшЬебгоп) из-за его связи с ассоциативным законом (14), доказанной в упражиеиии 27 (Ь). Ассоцивздр четвертого порядка, показаииый иа рис. 40, имеет три квадратные грави и шесть пятиугольных граней.
(Сравиите с рис. 23 из упражнеиия 7.2.1.2-60, иа котором показав "пермутаэдп" четвертого порядка, известное Архимедово тело.) Почему фигура иа рис. 40 ие входит в классический список одиородиых многогранников? 30. [М36[ Следом (ГооСрг)пФ) леса называется битовая строка Л... у„, определяемая следующим образом: Д = [узел у в прямом порядке обхода ие является листом), а) Если Р имеет след у1...
~„, какой след имеет г ~~ (см. упражнение 27)? Ь) Сколько лесов имеют след 10101101111110000101010001011000? с) Докавште, что у) = [с~у = О[, 1 ~ у < и, с использованием обозначений из (6). 6) Два элемента решетки вазываются комплемеишариммп (сошр1ешепсагу), если их наибольшая иижияя гравица представляет собой иижиий элемеит, а иавмеиьшая верхняя граница — верхний элемент.
Покажите, что Р и г" комплемевтариы в решетке Тамари тогда и только тогда, когда их следы комплемеитарвы в том смысле, что у1... У„', = Л... К„ь сделано для мги1илп$апаса.ого 52 КОМБИНАТОРНЫЙ ПОИСК м 31. [М88[ Бинарное дерево с п внутренними узлами называется вмрождеииььи (беЗепегасе), если его высота равна и — 1. а) Сколько и-узловых бинарных деревьев вырождено? Ь) В табл. 1, 2 и 3 мы видели, что бинарные деревья и леса могут быть закодированы при помощи различных п-кортежей чисел, Поясните для каждой из кодировок с|...с„, 81...д, е1...е„, lс1...8„, р|...р„, в1...в„, и1 ...и„и х1...э„, как можно при беглом взгляде на кодировку сказать, вырождено ли соответствующее бинарное дерево или нет, с) Истинно или ложно утверждение: если лес Р вырожден, то вырожден и Р~? 6) Докажите, что если и Р и Р' вырождены, то вырождены Г дР' = Р.1 Р' н Р1~ Р' = = РТР'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
