Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 29
Текст из файла (страница 29)
Т(в,х) = — аяС(х) С(ая) + хС(х) Т(в,х) + ияС(ая) Т(вх) = иу (С (х) — С (ия)) (1 — в) в((С(х) + С(вх) — 2)/х — (1+ в) С(х) С(ия) — (1 — в) (С(х) — С(ия))) (- )' Следовательно, Т „= « „— 2 ". СьС„ь. (Является ли данное доказательство комбинаторным7! Итак, /2т1/2ц+2 — 2т') 4т(я+1 — т)+и+1 1 1,т) 1, п+1 — т ) 2(п+1)(п+2) 2 60. (а) Это количество правых скобок в сов«омах. (Следовательно, это также количество )г, для которых вгь 1 с 0 в соответствующем "обходе червя".) (Ь) Для удобства положим 2«('(') = +1 н 2«(') ') = -1.
А1. (Инициализация.) Установить ! 2 — ) 2- 1 и (г — 2п. сделано для )аг!иьилн$анаса.ого и мы получаем формулу « „= (т + 1) С„е( — 2 «~ь™ е (гп — А) СьС ь — С . Теперь доказать, что ОТВЕТЫ К УПРАЖНЕНИЯМ 121 А2. [Выполненоу] Завершить работу алгоритма, если у > й. В противном случае установить а — '(', у — у + 1. АЗ.
[Атом?] Если Ь, = ')', установить в — — 1, 1 в+ 1 и перейти к шагу А4. В противном случае установить в — 1, 1 - 1+ 1 и, пока в > О, устанавливать а +- Ь;, 1 - у + 1, в — в + 4 (Ь,), 1 — 1+ 1. Вернуться к шагу А2. А4. [Соатом,] Установить в — в+ 4 (Ь,). Затем, если в < О, установить аь — Ьп й ~— — й — 1, 1 +- 1+ 1 и повторить шаг А4. В противном случае установить аь — ') ', й — й — 1, 1 — 1+ 1 и вернуться к шагу А2. 1 (с) Сбалансированная строка с дефектом 11, отображающаяся на строку (1)— (О)) ((О)) ) )) (О ((О) (О) ) (((. В общем случае мы находим такую строку, определяя индекс т непосредственно перед 1-й с конца правой скобкой и индексы (ие,ие),...,(и, мив 1) соответствующих друг другу скобок, такие, что и ~ т < < ив. 11.
[Инициализация.] Установить с — у — в - О, й — т — 2п н ие ~ — 2и + 1. 12. [Сканирование справа налево.) Если ав = ')', перейтн к шагу 13; если аь = '(', перейти к шагу 14; если й = О, перейти к шагу 15. 13. [Обработка ') ',] Установить г; — й,,у — у + 1, с - с + 1. Если с = 1, установить т — й — 1, в ~ — у и и, — й. Затем уменьшить й на 1 и вернуться к шагу 12. 14.
[Обработка '('.] (В этот момент левая скобка аь соответствует правой скобке а,, ) Установить ) — у — 1. Если г; > т, установить и — й и и. — гв.. Затем уменыпить й на 1 и вернуться к шагу 12. 15. [Подготовка к перестановке.] Установить 1 — ) — 1, й — 2п и с - О.
16. [Перестановка.] Пока у эв и„устанавливать Ь, — а,, 1 — 1+ 1, у — у + 1. Затем, если с = в, завершить работу алгоритма. В противном случае установить Ь; — ') ', ( — в' + 1„у —,у + 1. Пока й Вв и„устанавливать Ь, — аы ( — ю' + 1 и й — й — 1. Затем установить Ь; ~ — '(', 1 «- 1+ 1, й — й — 1, с +- с+ 1 и повторить шаг 16. 1 Примечание: тот факт, что дефект 1 (О < 1 < и) имеют ровно С„сбалансированных строк длиной 2п, был открыт П.А, Мак-Мэганом (Р.А, МасМайоп) [РЬНоворйса) Тгапвасяопв, 209 (1909), 153-175, $20], а затем повторно открыт К.Л.
Чангам (К.1. С)шпя) и В. Фолдером (%. Рейег) [Ргос. Хай Асад. Яс)., 35 (1949), 605- 608] с применением производящих функций. Простое комбинаторное пояснение было найдено позже Д.Л. Ходжесом (3,1,. Ноббев) [В(ошесгйа, 42 (1955), 261--262], котоРый заметил, что если 111... ~3, имеет дефект 1 > 0 и если (Уь = оьл — ее кРайний спРава соатом, то сбалансированная строка 61...
1)ь 1 Щ+1... 11,) аья имеет дефект 1 — 1 (и это преобразование обратимо). Эффективное отображение в данном упражнении похоже на конструкцию М.Д. Аткинсона (М.)). АВВпвоп) и Й.-Р. Сака (Л.-Н. Басй) [1п(огтавюп Ргосеввшй ьемегв, 41 (1992), 21-23[. сделано для мгвлидн$ана(а.ого 122 ОТВЕТЫ К УПРАЖНЕНИЯМ 61. (а) Пусть с = 1 — Ь", тогда с < 1, с~ + . + см = У и мы должны доказать, что утверждение с~+се+ +с» < 1 тогда и только тогда, когда Ь < Ф, справедливо ровно при 1 циклических сдвигах. Можно определить с; для всех целых г, полагая с +,ч = с .
Определим также Е; для всех,у„полагая Ее = 0 и Ез = Е, 1+ + с', тогда Е~+ьп = Е1 + уг и Е,+1 < Еу + 1. Отсюда следует, что для каждого целого х существует наименыпее целое у = з (х), такое, что Е = х. Кроме того, ,((х) < 1 (х + 1) и у (х + ~) = у (х) + Ф. Таким образом, интересующее нас условие выполняется тогда и только тогда, когда мы выполняем сдвиг на з (х) пюд Ю (где х = 1,2,...), нли на г". (История втой важной леммы рассматривается в ответе к упражнению 2.3.4.4-32.) (Ь) Начнем с 1 - гп — в — О. Затем для Ь: 1,2,, Ю (в указанном порядке) вытюлним следующие действия: установим з - з+ 1 — Ьь и, если з > гп, установим т — з, и — й и 1 — (1 + 1) пмх1 У. Ответом, согласно доказательству из ответа (а), будет уо 1у-ь (с) Начнем с произвольной строки Ь1 Ьз...
Ьн, содержащей пу значений 1, 0 < у < < с Применим случайную перестановку к втой строке, после чего применим алгоритм из ответа (Ь). Затем случайным образом выберем значение из Це,.,д-1) и используем результат циклического сдвига в качестве последовательности в прямом порядке обхода, определяющей лес. [См. 1. А1опео, Л.Е. Кенту ап4 Н. Бс1юьт, А)йог15йписа, 17 (1997), 162-182, где приведен еще более общий алгоритм.] 62. Битовые строки (11... 1„, г1 ...г„) корректны тогда и только тогда, когда строка Ь1...
Ь„, где Ь; = 1; + гу, корректна в упражнении 20. Следовательно, можно воспользоваться упражнением 61. (См. Л.Р., 1пгогщас)оп Ртосезз1пй Теыегз, 45 (1993), 64. Х = 26 + Ь, где (Й,Ь) = (0,1),(2,1),(0,0),(5,1),(6,0),(1,1); в конце 7сХ1 ...Ь1з = 5 11 3 4 0 7 9 8 1 6 10 12 2. 65. См.
А, РапЬо(тег ап4 Н. Рпхйпйег, Юмсге1е Масйещайсз, 250 (2002), 181-195; М. 1лсзах ав$ Р. %!пыег, Вапдогп Бггпсгигев аи4 А!1Оп$Ътв, 24 (2004), 420-443. 66. (а) "Сожмем" белые ребра, объединяя соединяемые ими узлы. Например, одиннадцати изображенным деревьям Шредера для и = 3 будут соответствовать обычные деревья Прн таком соответствии левая связь означает "зто дочерний узел", белая правая связь — "есть и другие дочерние узлы", а черная правая связь — "зто последний дочерний узел".
(Ь) Имитируем алгоритм Е, но между поворотами используем обычный код Грея для прохода по всем цветовым щаблонам имеющихся правых связей (в зтом упражнении данная последовательность проиллюстрирована для случая и = 3). сделано для ьтьуьк!п$апаса,ого 124 ОТВЕТЫ К УПРАЖНЕНИЯМ проста, насколько это возможно; однако для малых ! имеются более простые фор- мулы, наподобие М(»>„= М„+!, а кроме того, М!„—— 2" для 4 > и.) 72. Мы получим М,„, то же число, что и в предыдущем упражнении. В действи- тельности по индукции можно доказать, что существует ровно („"„) — (,",) строк длиной е+ и — 2>( > О, 73. 011001001000000000100101001100, 1П0010110111111111011010ШОО; см.
(38). 74. Согласно лексикографическому порядку, нужно подсчитать количество строк, крайние правые элементы которых имеют вид Ое»э, 10е»в, 110ь»т, 111000э»4, 11100100*»», 111001010е»», 11100101100е'э, 111001011010е!в, 1110010110110*!т, ..., те. всех 30-битовых строк, предшествующих т = 111001011011111111101101011100.
Если д имеет на р больше единиц, чем нулей, то количество строк шаблона рож- дественской елки, завершающихся битовой строкой де", равно количеству строк, завершающихся 1ге", и в соответствии с упражнением 71 равно М(р+П„, так как все такие строки являются потомками начальной строки Ог Ог !1 ... 1ю на и;м шаге. Следовательно, ответ на поставленный вопрос Ме(»э>+ Мц»э) + М»(»т> + Мц»4> + + ' ' '+ М(!»)3 + М(>3)» = 2 ь=! М(»ь-!-м)(в-х!) = О+ (»4) + (»4) + (>зт) + (!») + ' ' '+ + 8+ 4 = 84867708, где (»!,...,»ш) = (1,2,3,6,...,27,28) — последовательность позиций, в которых в т встречае»ся 1.
75. т, = М„», поскольку строка г, представляет собой нижнего потомка первой (в) (и) (в) (> 1~ строки в (33). Кроме того, г „, — г = М(„! ) — М(у 0(„» .> = МО+!>(„» 1) в соответствии с формулой из ответа к упражнению 74, поскольку соответствующая последовательяость»!... »„! для строки г("> — 1401" ' !. Следовательно, посколь- ку М>„/̄— ! / для фиксированного значения у при и — оа, мы получаем г( ) >г у+2 йш -( — =~ — =1 — » —, в ао М„~-~ 2»+! 2»+» ' $=! Мы также неявно доказали, что ~ >", е Мь( ~-ь) = Мч+! — 1.
76. Первые (»„") элементов бесконечной последовательности Я = 1313351313351335355713133513133513353557131335133535571335355735575779., представляют собой размеры строк в п»аблоне порядка 2а; эта последовательность Я = д»д»дз... является единственной фиксированной точкой преобразования, отображающего 1 13 и и ! (и — 2) пп (и + 2) для нечетных и > 1, представляющего собой два шага из (36). Пусть /(з) = йшв>р„э(>хМ„1)/и при О с к с 1. Эта функция, по-видимому, почти везде стремится к нулю; однако она равна 1, когда х имеет вид (д! + + д )/2", в соответствии с ответом к упражнению 72.
С другой стороны, если мы определим д(х) = Бш„э(~зМ„))/>/й, то функция д(х) является изме! римой, с ) е д(з) !(х = >~~, хотя д (з) бесконечна, когда /(х) > О. (Строгое доказательство или опровержение этих гипотез пока отсутствует.) 77. Указание следует из (39) при рассмотрении обхода червя; так что мы можем действовать следующим образом. сделано для эуэлкиИанаса.ого 7.2.1 ОТВЕТЫ К УПРАЖНЕНИЯМ 125 Х1. [Инициализация.[ Установить а — 0 для О < у < и; установить также х — 1. (На последующих шагах х = 1 + 2 (а1 + + а„).) Х2. [Коррекция хвоста.) Пока я < и, устанавливать а — 1 и х — х + 2.
ХЗ. [Посещение.[ Посетить битовую строку а|... а„. Х4. [Простой случай?) Если а„ = О, установить а„ вЂ” 1, я — л + 2 и вернуться к шагу ХЗ. Хб. [Поиск и продвижение а-.[ Установить а„— 0 и у — и — 1. Затем, пока а = 1, устанавливать а — О, х — х — 2 н у — 1 — 1. Завершить работу, если 1 = 0; в противном случае установить а — 1 и вернуться к шагу Х2. 1 78. Истинно согласно (39) и упражнению 11. 79.
(а) Перечислите индексы нулей, затем индексы единиц; например, битовая строка из упражнения 73 соответствует перестановке 1 45 7 8 10 11 12 13 20 23 25 2930 2 3 6 9 14 15 16 17 18 19 21 22 24 26 27 28. (Ь) Диаграмма Р содержит в верхней строке индексы левых скобок и свободных скобок (пользуясь обозначениями из (39)); остальные индексы находятся во второй строке. Таким образом, из (38) [См, в К.-Р.
Уо, ЯХАМ,7. А18ебгшс апб Пмсгеге МеФЬобз, 2 (1981), 324-332, обобщение для цепочек подмультнмножеств.[ 80. Этот любопытный факт является следствием упражнения 79 совместно с теоремой 6 из статьи автора о диаграммах [см. РасЬЗс 7. МаСЬ., 34 (1970), 709--727[. 81. Предположим, что и и и' принадлежат соответственно цепочкам длиной з и з' в шаблонах рождественской елки порядка п и и'. В биклаттере могут находиться на более ппп (э, з') из зе' возможных пар строк из этих цепочек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
