Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 12
Текст из файла (страница 12)
в 32. [М88[ Докажите, что если Р -1 Р', то существует лес Р", такой, что для всех С Р' 1.С = Р тогда и только тогда, когда Р -1 С -1 Р", Следовательно, в решетке Тамари выполняются пааудистрибитивнме законы: из Р.1.С = Р.1.Н вытекэат Р.1. (СТН) = Г1С; из РТС = РТН вытекает РТ (СЛН) = .ГТС. ° ЗЗ. [М87] (Представление деревьев при памои1и перестановок.) Пусть о — цикл (1 2... п).
а) Докажите, что для заданного бинарного дерева, узлы которого пронумерованы от 1 до и в симметричном порядке обхода, существует единственная перестановка Л множества (1,..., и), такая, что для 1 < Й < и ~[8Л, если йЛ < й; (О в противном случае; [йоЛ, если ЬтЛ > й; ~О в противном случае. Таким образом, Л упаковывает 2п полей связей в единый п-элементный массив. Ь) Покажите, что эту перестановку Л наиболее легко описать в циклическом виде, когда бинарное дерево является представлением левый брат/правый потомок лес» Р.
Как выглядит циклический вид Л (Г) для леса (2)? с) Найдите простое соотношение между Л (Р) и дуальной перестановкой Л (Р"~). 6) Докажите, что в упражнении 26 Р' покрывает Р тогда и только тогда, когда Л (Р') = (~ к) Л (Р), где у и )с — братья в Р, е) Следовательно, количество максимальных цепочек в решетке Кревераса порядка и равно количеству способов разложения и-цикла в виде произведения п — 1 перестановок. Вычислите это значение. Указание: см. формулу 1.2.6-(16). сделано для мгнцалп$апаса.ого 7,2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОВЪЕКТОВ 53 34. [Мйй[ (Р.П. Стенли (Н.Р. Втап1еу).) Покажите, что количество максимальных цепочек в решетке Стенли и-го порядка равно (и(п — 1)/2)!/~1" ~3" ~...
(2п — 5) (2п — 3) ). 35. [НА?[ (Д.В. Тайлер (В.В. Ту1ег) н Д.Р. Хикерсон (В.Н. Н1скегвоп).) Объясните, почему все знаменатели в асимптотической формуле (15) являются степенями 2. ° 36. [Мл5[ Проанализируйте алгоритм генерации тернарных деревьев из упражнения 20 (Ь). Указание: в соответствии с упражнением 2.3.4,4-11 имеется (2п + 1) ' (з„) тернарных деревьев с и внутренними узлами. ~ь 37.
[М40[ Проанализируйте алгоритм Закса-Ричардса для генерации всех деревьев с данным распределением по, им пз,..., и» степеней (см. упражнение 21). Указание: см. упражнение 2.3.4.4-32. 36. [Мхй[ Чему равно общее количество обращений к памяти, выполняемое алго- ритмом 1, выраженное как функция от п? 39. [хх[ Докажите формулу (23), показав, что элементы А в (5) соответствуют диаграмме Юнга с двумя строками.
40. [Мйй[ (а) Докажите, чтоСр» нечетнотогдаитолькотогда, когдар Зс (7+1) = = О, т.е. когда бинарное представление р и д+ 1 не имеют общих битов. (Ь) Следовательно, С„нечетно тогда и только тогда, когда п + 1 представляет собой степень 2. 41. [М31[ Покажите, что баллотировочные числа имеют простую производящую функцию [ Ср,»рех». ~ 42. [Мйй[ Сколько непомеченных лесов с и узлами являются (а) самосопряженными; (Ь) самотранспонированными; (с) самодувльными? (См. упражнения 11, 12, 10 и 26.) 43.
[Мх1[ Выразите Ср» через числа Каталана (Са, СмС»,...). Целью является получение простой формулы для малых величин д — р. (Например, С1» з1» = ѻ— С» — г ) ° 44. [Мх7[ Докажите, что алгоритм В делает 81»+О (и ') обращений к памяти на одно посещенное бинарное дерево. 45. [М36[ Проанализируйте обращения к памяти, выполняемые алгоритмом нз упражнения 22.
Сравните полученное значение со значением для алгоритма В. 46. [МЗО[ (Обобщенные числа Ка»палена.) Обобщим соотношения (21), определив С,„(х) =Ср1 О(х)+х' рС(р 0»(х), если 0<р<а»ьО; Ссо(х) =1; и Ср» (х) = О, если р < О пли р > д; таким образом, Ср» —— Ср (1). Пусть также С„(х) = С„„(х), так что (С ( ),С (х),...) = = (1,1,1+ х,1 + 2х+ хт+ хз,1+ Зх+ Зх~+ Зхз+ 2х~+ ха+ ха,...) . сделано для ьуькьиЛп7апаса.ого 54 КОМБИНАТОРНЫЙ ПОИСК а) Покажите, что [х"1 С (х) -- количество путей от (Я) до ~~ф в графе (28), которые имеют площадь |с, где "площадь" пути представляет собой количество прямоугольных ячеек иад иим.
(Таким образом, 1 образный путь имеет максямальио возможиую площадь, равную р(й — р) + ф).) )з) Докажите что С (х) ~' хе|+- +с ~ длина внгтРееиего пУтн(Р) берется по всем и-узловым лесам Е. с) Покажите, что если С(х,х) = 2 ~ рС„(х)х", то С(х,х) = 1+ уС(х,л) С(х,ху). д) Кроме того, С(х,х)С(ххх)...С(ххгх) = 1 сС <р+ 1(х)хР. 47. (М871 Продолжая предыдущее упражиение, обобщите тождество (27). 48. (М88) (Ф. Раски (Р. Нпвкеу) и А. Проскуровски (А, Ргоз)гпгоиеЫ).) Вычислите С„(х) при х = — 1 и яспользуйте полученный результат для того, чтобы показать, что "идеальный" код Грея для аложениых скобок иевозможеи при нечетном и > 5. 49. (17! Какова миллиоииая в лексикографическом порядке строка, состоящая из 15 вложенных пар скобок? 50.
[36) Разработайте алгоритм, обратный алгоритму 1): для данной строки вложеииых скобок а1... аз„ои должен определять ее ранг 1'у' — 1 в лексикографическом порядке. Чему равен рввг (1)? 51. (М88) Пусть хауз... х„— дополнение х~хз... у„до 2п; другими словами, 3 = = 2п — ху, где х определено в формуле (8). Покажите, что если Х1 Хз... х„— (зу' + 1)-е и-сочетаиие (0,1,...,2п — 1), сгенерированное алгоритмом 7.2.1.3Ь, то х|хз...
»„ является (Ю вЂ” к„Я+ 1)-м и-сочетапием (1,2,...,2п), сгеиерироваииым алгоритмом из упражиеиия 2. (Здесь к„озиачает и-ю фуикцию Крускала, определенную в 7.2.1.3-(60).) 52. (М38) Найдите среднее и дисперсию величины 4, в табл. 1 при случайиом выборе строки вложеиных скобок а1... ау„, 53. (М88] Пусть Х вЂ” расстояние от корня расширенного бинарного дерева до край- него слева внешнего узла. а) Каково математическое ожидание значения Х, если все бинарные деревья с и узлами равиовероятпы? Ь) Каково математическое ожидание зиачеиия Х в случайном бикерпом дереве поиска, построенном с использованием алгоритма 6.2.2Т иа основе случайной перестаиовки К1...
К„? с) Каково математическое ожидание значения Х в случайном вмрохсдекяом (в смысле упражнеиия 31) бинарном дереве? д) Каково математическое ожидаиие зиачеиия 2х во всех трех случаях? 54. (х(М88) Чему равио математическое ожидание и дисперсия с1+ . +с„(см. уп- ражиеиие 46)? СДЕЛаНО ДЛЯ Мгаж1П$анаСа.ОГЦ 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМВИНАТОРНЫХ ОБЪЕКТОВ 55 55. [НМЮЮ[ Вычислите С,' (1) — обшую площадь всех путей в упражнении 46 (а). 56. [Мйу] (Ренцо Спруньоли (Вепво Вргпйпо)1), 1990.) Докажите формулу сумми- рования 2т — и /2т'1 /2и — 2т'1 2 2 ( 1)~ )~ С,С„,, = -С„+ ) для <т<п. 2п (и+ 1) [~ т ) ~ п — т ) ь=о 57.
[Мвв[ Выразите суммы Н„(а, Ь) = 2" о (,~ „) ( з ь)Ь' в аналитическом видедля р = О, 1, 2, 3 и используйте полученные формулы для доказательства формулы (30). 58. [НМ34[ Обозначим через Ъ „количество и-узловых бинарных деревьев, в которых внешний узел ти (при нумерации внешних узлов от 0 до и в симметричном порядке обхода) находится на уровне 1. Пусть также 8 „= 2 ~", 10 „, так что г „/С вЂ” средний уровень внешнего узла т; и пусть 1(и, в) — сверхпроизводящая функция 1»ш™в" = (1+ ш) л+ (3+ 4в+ Зш~) в~ + (9+ 13ш+ 13ш~ + йш~) аз + Докажите, что и выведите простую формулу для чисел $,»».
59. [Нар[ Аналогично: пусть Т~ „— количество всех и-узловых бинарных деревьев, в которых внутренний узел т находится на уровне 1. Найдите простую формулу для Т,„» = ~~ ~ (Ть»». ь 60. [Мйб[ ( Сбалансированные строки.) Строка вложенных скобок а является аиюлаариой (асош1с), если она имеет вид (о'), где о' — строка вложенных скобок.
Каждая строка вложенных скобок может быть единственным образом представлена как произведение атомов о1... о„. Строка с одинаковым количеством левых н правых скобок называется сбалансированной (Ъа)лисео). Каждая сбалансированная строка может быть единственным образом представлена в виде 111... б„, где каждан подстРока 111 ЯвлЯетсЯ либо атомом, либо соатомам (со-атош) (обРащением атома). Дефектом (ое1есС) сбалансированной строки является половина длины ее соатомов. Например, сбалансированная строка ( ( ) 1 )( ( ( ) ) > 1 1 1 1( ) С С( ) > С < ( > 1 ( С ) имеег разложение р!АФЗр4д5Фвргдв = о1пз озсг4 оз аоот юв, с четырьмя Отомкни и четырьмя соатомами; ее дефект равен [озо4аопт[~2 = 9.
а) Докажите, что дефект сбалансированной строки равен количеству индексов к, для которых й-я правая скобка предшествует Й-й левой скобке. сделано для зивлк$п(апаса.ого 66 КОМБИНАТОРНЫЙ ПОИСК 7.2.1 Ь) Если строка Д... 0, сбалансирована, ее можно отобразить на строку вложенных скобок простым обращением соатомов. Однако описанное далее отображение более интересно, поскольку производит несмещенные (случайные равномерно распределенные) строки вложенных скобок из несмещенных сбалансированных стРок. ПУсть имеетсЯ в соатомов бц = ал, ..., Д. = аль.
Заменим каждый соатом на '('; затем добавим строку ) а'; ... ) а,',, где ау = (а'). Например, строка, приведенная выше, отображается на строку а1(аз((ав(ав)аг)ав)аа)ав, которая представляет собой строку (1) из начала данного раздела. с) Разработайте алгоритм, который применяет описанное отображение к заданной сбалансированной строке 61...
6р„. д) Разработайте также алгоритм для обратного отображения: для данной строки вложенных скобок а = а1... ав„и целого числа 0 < 1 < и он должен находить сбалансированную строку р' = Ь1... Ьз„, дефект которой равен! и которая отображается на строку а. Какая сбалансированная строка с дефектом 11 отображается на строку (1)? в 61. [М26[ (Лемма Рани ~Наиву) о цикле.) Пусть 6|Ьв... Ьл — строка неотрицательных целых чисел, такая, что ) = Ф вЂ” 61 — Ьв — ° ° . — Ьл > О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
