Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 15
Текст из файла (страница 15)
упражнение 13)7 64 КОМБИНАТОРНЫЙ ПОИСК 7.2Л ° 116. [88[ Если узлы леса Р помечены от 1 до и в прямо-обратном порядке, то будем называть узел й (1 < й < и) еезрчны (1пску), если он смежен с узлом я+ 1 в Р; ясесзрчам (пп(иску), если он удален на три шага; обмчямм (огбшагу) в противном случае. При таком определении узел и + 1 представляет собой воображаемый супер- корень, рассматриваемый как родительский для каждого корня. а) Докажите, что везучие узлы располагавпся только на четных уровнях, а невезучие — только на нечетных.
Ь) Покажите, что количество везучих узлов ровно иа один больше количества невезучих узлов, кроме случая и = О. 117. [81] Сколько и-узловых лесов не содержат невезучих узлов? 118. [М88[ Сколько везучих узлов имеется (а) в полном г-арном дереве с (г" — 1)/ /($ — 1) внутренними узлами; (Ь) в дереве Фибоначчи порядка я, с ге+1 — 1 внутренними узлами? (См. 2.3л.б-(6) и рис. 8 в разделе 6.2.1.) 119. [81[ Скррченнос бинамнвлэное дерево Т„порядка и определяется рекурснвно правилами Те= °,т„ при и > О. ?» -1 М Т,' (Сравните с 7.2.1.3-(2Ц; мы обращаем порядок дочерних узлов на чередующихся уровнях.) Покажите, что прямо-обратный обход Т„имеет простую связь с бинарным кодом Грея.
120. [88[ Истинно нли ложно утверждение: квадрат графа гамильтонов, если граф связный и не имеет мостов? 121. [МЦ[ (Ф. Нойман (Р. Хецшап), 1964.) Производной графа С называется граф с»<'>, полученный путем удаления всех вершин степени 1 и ребер, которые с ними соединены. Докажите, что если Т вЂ” свободное дерево, то его квадрат Т~ содержит гамильтонов путь тогда и только тогда, когда его производная не имеет вершин степени, большей 4, и выполняются два следующих условия: () все вершины степени 3 или 4 в Т~б лежат на единственном пути; й) мемеду любыми двумя вершинами степени 4 в Т(0 есть, как минимум, одна вершина, степень которой в Т равна 2. 100=1+2х3+4хб-6+7+Зх9= = (1 + 2 — 3 — 4) х (5 — 6 — 7 — 8 — 9) = = ((1?((2+3)/4 — 6+6)) х 7+8) х 9.
сделано для ьтькж1пГапаса.ого ° 122. [31) (Голоеоламка Дьюдснп (Т)иг(епсй) о прсдстлаелснпи сотни.) Имеется много интересных способов представить число 100 путем вставки арифметических операторов (и, возможно, скобок) в последовательность 1234М789, например: 7.2,1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБЪЕКТОВ 65 а) Сколько имеется таких представлений числа 100? Чтобы сделать этот вопрос точным, с учетом закона ассоциативности и других алгебраических свойств будем считать, что выражения записываются в каноническом виде в соответствии с приведенным далее синтаксисом, (ехргевьйоп) — (пшпЬег) 1 (впш) / (ргобпсс) / (срюнепс) (ысгп) (сепп) + (сегш) ~ (гегш) — (гегш) 3 (впш) + (гегш) $ (вппз) — (сегш) (гегш) — (пшпЬег) ( (ргодпсс) ) (с~пог1епФ) (ргос(пес) — (Еассог) х (Еасгог) $ (ргобпсс) х (Еассог) ! ((срюнепг)) х (йссог) (срюнепг) — (йсгог)/(Еассог) ! (ргобпсг)/(Еассог) ~ ((цпонепс))/(йссог) (Еасгог) — ~ (пшпЬег) ) ((впгп)) (пшпЬег) — (бйрг) Используемые цифры — от 1 до 9 в указанном порядке.
Ь) Расширим задачу (а), допуская использование чисел, состоящих из нескольких цифр: (пшпЬег) - (сИрс) ) (пшпЬег)(с((рс) Например, 100 = (1/(2 — 3 + 4)) х 567 — 89. Какое из таких представлений наиболее короткое и какое наиболее длинное? с) Расширим задачу (Ь), допуская использование десятичной точки: (шппЬег) — (61рг всппй) ~ . (61рг вгпп8) (618К в1гш8) — (618К) ! (Йрг всг(п8)(61рФ) Например, 100 = (.1 — 2 — 34 х .5)/(.б — .789).
123, Щ Продолжая предыдущее упражнение, ответьте, каковы наименьшие положительные целые числа, которые не могут быть представлены с использованием соглашений (а), (Ь) и (с)? В 124. (40) Эксперимент с методами черчения расширенных бинарных деревьев, вызванный простыми природными моделями.
Например, мы можем назначить каждому узлу х значение с (х), именуемое числом с«ортона-Сслрахлера (Ноггоп — ЯсгаЫег пшпЪег), следующим образом. Каждый внешний узел (лист) имеет значение п(х) = 0; внутренний узел с дочерними узлами (Е,г) имеет значение е(х) = снах (и (1), в (г))+[и (Е) = е (г )). Ребро от внутреннего узлах до его родителя можно изобразить как прямоугольник высотой Ь (е (х)) и шириной и (в (х)), а прямоугольники ребер к дочерним узлам (1, г) могут быть повернуты на углы д (е (1 (х)), е (г (х))) и — д(э(г(х)), в(1 (х))) для некоторых функций Ес, сс н 9. На рис. 42 показаны типичные результаты при выборе ю (Ес) = 3+ л, Ь (й) = 18)с, д «Ес, Ес) = 30, д(у, к) = = ((Ес + 1)Д) х 20' для 0 < й < у и д (у, сс) = ((Ес — у)/Ес) х 30' для 0 < Е < к; корни находятся внизу.
На рис. 42,а показано бинарное дерево (4)„на рис. 42,б — случайное 100-узловое дерево, сгенерированное алгоритмом И; на рис. 42,в — дерево Фибоначчи 11-го порядка со 143 узлами", а на рнс. 42,г представлено случайное 100- узловое бинарное дерево поиска. (Очевидно, что деревья б-г относятся к различным видам.) сделано для вувгсж$ВЕанаса,ого 66 комвинлторный поиск !! б Рис.
42. "Органические" бинарные деревья сделано для мчлрдп1апаФа.огя 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБЪЕКТОВ 67 (Эта темв1 связвнв почти со всеми полезными знаниями, которые только может воспринять человеческий рвэум. — Якоб бернулли 1'.5эпзеэ Ветпоий!) . дтв Со7йестапсзз' 1'Искусство догвдки) 1'1713) 7.2.1.7 Исторические и иные сведения Ранние работы по генерации комбинаторных шаблонов начались вместе с зарождением цивилизации. Это очень интересная история, н, как мы увидим, она охватывает многие части мира и многие области человеческой деятельности, включая поэзию, музыку и религию, Здесь будут рассмотрены только некоторые основные вопросы, но такой краткий экскурс в историю не может не стимулировать интерес читателя и не подвигнуть его на более глубокое изучение данной темы.
Списки всех кортежей из п элементов прослеживаются тысячи лет назад в древних Китае, Индии и Греции. Наиболее примечательный источник (в силу того, что эта книга в современном переводе стала бестселлером) — это китайская 1 С)ззпй, или Узззпй, что означает "Книга изменений". В этой книге, одной из пяти классических книг конфуцианства, содержится ровно 20 = 64 главы, каждая глава символизирует гексаграмму, образованную из шести линий, каждая из которых имеет вид либо ("инь"), либо — ("ян"). Например, гексаграмма 1 состоит нз линий ян йй(, гексаграмма 2 — из линий инь йй„а гексаграмма 64 представляет собой чередующиеся ян и инты П. Вот полный список гексаграмм: 6 7 4 йй йй П П 2З М Я й"й йй 39 39 40 ЙЖ йй Йй М ы- и 25 26 й'й йй !! 32 33 Ы йй Е 2'! 2929 П ш кй 34 и 36 ййй йИ й 2 З Йв йй Йй Й ~й йй 49 50 5! йй й0й И й йбй Е 42 М И и 59 69 6! й(й я йЗ 57 56 СДЕЛаНО ДЛЯ звгажПИавата.ОГй Такое размещение 64 возможных вариантов называется упорядочением Кинг Веня, так как авторство книги 1 С)ипй приписывается Кинг Веню (К)пб %еп) (около 1100 года до н.
э.), легендарному основателю династии Чу. К сожалению, древние тексты трудно надежно датировать, так что современные историки не видят оснований считать, что такой список гексаграмм был составлен ранее 1П века до н. э. Обратите внимание, что в перечне (1) гексаграммы располагаются парами: за гексаграммой с нечетным номером идет гексаграмма, представляющая собой зеркальное отражение относительно горизонтальной оси, кроме случаев, когда гексаграмма симметрична„— в этих случаях гексаграмма спарена со своим дополнением (1 = 2, 27 = 28, 29 = 30, 61 = 62). Гексаграммы, состоящие из двух триграмм, представляющих четыре основных элемента — воздух (ии), землю (ив), огонь (ий) н воду (йй), также размещаются специальным образом. Остальные гексаграммы размещаются по сути случайным образом.
Определенные шаблоны, существующие в расположении пар, ие более чем совпадения, подобные совпадениям в записи числа 77 (см. 3.3-(1)). Инь и ян представляют собой взаимодополняющие стороны элементарных сил природы, всегда находящиеся в противоборстве и переходящие друг в друга. В опре- 68 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 деленном смысле 7 СЫп8 представляет собой тезаурус, в котором гексаграммы служат указателями к накопленным знаниям о фундаментальных концепциях наподобие следующих: давать ($ж) или получать ($$), скромность ($$), радость (~), товарищество ($1$), изъятие ($!$), мир (М), война ($!$), организация ($$), коррупция ($!$), незрелость (я$), изящество (Б) и тд.
Можно выбрать пару гексаграмм случайным образом, получая вторую из первой, например независимо заменяя каждый инь на ян н наоборот с вероятностью 1/4; такой метод дает 4096 способов размышлений об экзистенциалистских загадках, например: не может ли соответствующий марковский процесс приоткрыть тайну смысла жизни? Строгий логический способ упорядочения гексаграмм был дан около 1060 года н. э. Шао Юнгом (8Ьао Уппй).
Его лексикографическое упорядочение от $$ к $$ к $$ к $$ к $$ к ... к йи к И (каждую гексаграмму надо читать снизу вверх) существенно более понятное, чем порядок Кинг Веня. Когда Г.В. Лейбниц (С.И!. Ье!Ьп!г) изучал зту последовательность гексаграмм в 1702 году, он пришел к ложному выводу о том, что китайские математики были знакомы с бинарной арифметикой. [См. Ргапй 8ие1г, МаВЬешабсв Мабагше, 76 (2003), 276-291. Дополнительную информацию об 7 СЬ!л8 можно найти, например, в ЛоверЬ Ыее(Ьаш Вс!енсе алд С!т1- !1яаг!оп !и СЫпа 2 (СатпЪгн18е !)и!тегв!1у Ргсев, 1956), 304-345; И,Л. 1,упп, ТЬе С!авв!с ог" СЬапбш (Хек Уогй: Со!шпЬ!а 1!и!тегв!гу Ргевв, 1994).) Другой древнекитайский философ, Янг Пинг (Уапб Нвшпй), предложил систему, основанную на 81 тернарной тетраграмме, вместо 64 гексаграмм.
Его Канон высшего таинства (Салоп ог" Яиргеше Мувгегу), написанный около 2 года до н. з., не так давно был переведен на английский язык Майклом Найланом (М!сЬае! Ну1ап) (Хеэг Уогй: А1Ъвпу, 1993). Янг описывает структуру полного иерархического тернарного дерева, в которой имеется три края, по трн провинции в каждом крае, по три департамента в каждой провинции, по три семьи в каждом департаменте, и по девять коротких стихов на семью — итого 729 стихов, т.е, почти в точности два стиха на калсдый день года. Его тетраграммы располагаются в строгом лексикографическом порядке при чтении сверху вниз: М, Н, Ю, Ш, гн, .-г, ==ч ..., 1Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
