Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 30
Текст из файла (страница 30)
Кроме того, с учетом (39), эти зз' пар строк в действительности при конкатенации образуют ровно пил(», е') цепочек в шаблоне рождественской елки порядка и+ и'. Таким образом, сумма пйп (з, з') по всем парам цепочек равна М„+„, что и дает искомый результат. Кстати, при этом мы доказали неочевидное тождество ппп (т+ 1 — 2[, и+ 1 — 2Ь) Ся„,,)С~(„Ю = М,„+„. ул Примечание: это расширение теоремы Спернера было доказано независимо Г. Катоной (С.
КаФопа) [осийа Ясб МагЬ. Нпп8аг., 1 (1966), 59-63[ и Д. Кляйтманом (П. К1е$1шел) [МагЬ. Яейжйгюй, 90 (1965), 25 1-259[. Доказательство из этого упражнения и некоторые дополнительные результаты приведены в Сгеепе апб К1еашап, ,7. СотМпагог!а( ТЬеогу, А20 (1976), 80-88. сделано для иькьнЛВ$анаса,огя 7.2.1 126 ОТВЕТЫ К УПРАЖНЕНИЯМ 82. (а) Существует, как минимум, одно вычислеиие в каждой строке т; их два тогда и только тогда, когда б (т) > 1 и первое вычисление дает О. Таким образом, если « тождественно 1, мы получаем мииимум, М„; если «тождественно О, мы получаем максимум, М„+ 2„(б (т) > 1) = М„тс.
(Ь) Пусть «(1( (т, и/2)) = 0 в С„сз случашс„когда б (т) = 1; в противиом случае пусть «(1((т„а)) = 1, где а определяется алгоритмом. Когда и нечетко, из этого правила вьпекает, что «(о) всегда равио 1; ио когда и четко, «(сг) = 0 тогда и только тогда, когда о — первая битовая строка в своей строке. (Чтобы понять, почему это так, воспользуйтесь тем фактом, что строка, содержащая о( в формуле (41), всегда имеет размер б — 2.) Эта функция «в действительиости монотонна; если а < т и если о имеет свободные левые скобки, то же справедливо и для т.
Например, в случае и=8 мы имеем «(хс~ ° ° ~хб) = хб Ч ябхт Ч ясхб (хб Ч хт) Ч азха (яб (хб Ч за Ч хе) Чхе (хб Ч х; )) . (с) В этих обстоятельствах фуикция (45) является решением для всех и. 83. На шаге Н4 возможно ие более 3 исходов, иа самом деле ие более 2 при б (т) = 1. (См, более строгие границы в упражнении 5.3.4-31; в обозначениях из этого упражиеиия имеется ровно 6„+2 моиотоииых булевых функций от и булевых переменных.] 84.
Разобьем 2" битовых строк вместо цепочек иа М„блоков, причем строки (ас,..., о,) каждого блока удовлетворяют условию )) Аоу — АоЦ > 1 при с ~ «; тогда условию ))Аат — Ь)) < 1«2 могут удовлетворять ие более одной битовой строки в каждом блоке. Пусть А' обозначает первые и — 1 столбцов А„» е — и-й столбец. Предположим, что (ос,..., о„) — блок А', при этом количество индексов таково, что егА'отс минимальио среди всех егА'сгт. Тогда правило (36) определяет соответствующие блоки для А, поскольку ~~А(асО) — А(а10) )~ = (~А(ос1) — А(о11) ~~ = ~~А'о~ — А'оД )г 4( 0)~1~~ бА т+„А т((~ =~~А'(о — о,)~~~ +)!е)!~+2етА'(сгз — ос) >!)е)1 >1.
[Справедливо и многое другое; см. Ас)еапсеб )п МаСЬ., 5 (1970), 155-157. Этот результат является расширеиием теоремы Д.Э. Литлвуда (З.Е. )асс!лоос)) и А.С. Оффорда (А.С. Ойогс)), Мас, БЬогпск, 54 (1943), 277-285, которые рассмотрели случай т = 2.! 85. Если Ъ' имеет размерность и — т, можно перенумеровать координаты так, что (1, О, ..., О, хм, ..., хс) (О, 1, ..., О, ш, ..., х ) ® 0» 1~ х(я-сия 1 ~ Я(и-пь)пь) сделано для эеэеьеЛпГапаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 127 7.2.1 представляет собой базис, в котором ни один вектор-строка е = (хч,...,х,„) не состоит из нулей. Пусть е„+1 = (-1, О,..., О), ..., е„= (О, О,..., — 1). Тогда количество 0 — 1 векторов в У равно количеству 0 — 1 решений Ах = О, где А — матрица размером ги х и со столбцами оы..., о„.
Но эта величина не превосходит количество решений [[Ах[[ < 1 ппп Це|[[,..., [[еч[[), которое, согласно упражнению 84, не превосходит М„. И обратно: базис с гп = 1 и х 1 = (-1)1 ' дает М„решений. [Этот результат имеет применение в электронном голосовании; см. диссертацию Голля на соискание ученой степени РЬ.П. (81элгого, 2004).] 86. Сначала переупорядочим 4-узловые поддеревья так, чтобы их коды уровней представляли собой 0121 (плюс константа); затем будем сортировать все болыпие и большие поддеревья, пока все они не станут каноническими. В результате мы получим коды уровней О 1 2 3 4 3 2 1 2 3 2 1 2 0 1, а оютветствующими указателями на родительские узлы являются 0 1 2 3 4 3 2 1 8 9 8 1 12 0 14.
87. (а) Условие выполняется тогда н только тогда, когда с1 « ° ° сь > сь+1 » ° ° > с„для некоторого Й, так что общее количество таких ситуаций равно 2 ь („" „) = ув-1 (Ь) Заметим, что с1... сь = с',... сь тогда и только тогда, когда р~... рь = р[... р~ь', в таком случае сь.~.г < сь, тогда и только тогда, когда рьег < рь+,. 88. Посещается ровно А„ег лесов, и у А» из них рь = ° = р„= О. Следовательно, шаг 04 выполняется А„рэз; рь на шаге 05 изменяется Аь+1 — 1 раз прн 1 < й < < и.
Швг 05 также изменяет р„всего А„— 1 раз. Среднее количество обращений к памяти на одно посещение, таким образом, составляет 2+ 3/(а — 1) + О (1/и)— ю 3.534, если хранить р„в регистре. [См. Е. КпЬ(сйа, СошЬйа1онсэ, РгоЬа)лЬ1у апд Сошрпэшй, 5 (1996), 403-417.[ 89. Если на шаге 05 прнсваивание р„— р выполняется ровно О рвз, то присванвание рь — р. выполняется Оь + Аь+1 — Аь раз для 1 < й < и, поскольку каждый префикс канонического р1...р„является каноническим.
Таким образом, получаем (Оы аз,...) = (0,0,1,2,5,9,22,48, 118,288,...); можно показать, что О„= = Еэ>1Е1<,<„~4 1а~ — ад - э-,о, где ам — количество канонических родительских последовательностей р1...р„с р„= й. Однако сами значения а„ь пока что остаются загадкой. 90. (а) Это свойство эквивалентно 2.3.4.4-(7); вершина 0 является центроидом. (Ь) Пусть т = [п/2). Требуется внести следующие изменения. В конце шага 01 установить р +1 - О, а также рэ +~ - О, если п нечетно. В конце шага 04 установиты — у и, пока р; ф О, устанавливать 1 — р;.
(Тогда 4 является корнем дерева, содержащего у и й.) В начале шага 05, если й = 4 + гп и 1 <,у, установить у е-1и о -гп. (с) Если и четно, бицентроидных деревьев с п + 1 вершинами не существует. В противном случае найдем все пары (р[...р',р",...р" ) канонических лесов из гп = [и/21 узлов, где р~1...р' > р~'...р"; пусть р1 = О, р +1 — — р' + 1 и р е +1 = = (р," + го + 1) [р" > 0~ для 1 < у < гп. (Все такие последовательности будут сгенерированы двумя реализациями алгоритма О. Такой алгоритм для свободных деревьев разработан Ф.
Раски (Р. Кпэ$сеу) и Г. Лн (О. 13) [см. ВОЙ, 10 (1999), 8939- 8940[.) сделано для вью! п$апаса.ого 128 ОТВЕТЫ К УПРАЖНЕНИЯМ 91. Воспользуемся следующей рекурсивной процедурой И' (и). Если а < 2, процедура возвращает единственное п-узловое ориентированное дерево. В противном случае выбираются положительные целые числа.1 и 8 так, что данная пара (.у, 4) получается с вероятностью 8А,~А„уз/((п — Ц А„).
Вычислшотся случайные ориентированные деревья Т' — И'(и — м1) и Т" - И'(8). Возвращается дерево Т, полученное путем связи ) копий Т" с корнем Т'. )СотЬ1пагона1 А18опг)ипз (Асадеш1с Ргеэв, 1975), глава 25.) 92. Не всегда. )Р.Л. Камминс (К.1 . Сшппппз) доказал в )ЕЕЕ Тгапв. СТ-13 (1988), 82-90, что граф 8 (С) всегда содержит цикл; см. также С.А. Но1вшапп апй Р.
Натягу, НАМ Х Аррйед Май., 22 (1972), 187 — 193. Однако их построение непригодно для эффективного вычисления, поскольку требует предварительной информации о четности размеров промежуточных результатов.) 93. Да. Шаг 87 аннулирует шаг 83, а шаг 89 аннулирует удаление на шаге 88. 94. Например, можно воспользоваться поиском в глубину с использованием вспомогательной таблицы Ь1... Ь . 1) Установить Ь1... Ь„- 0... О, затем установить е +- 1, ю - 1, 6~ — 1 и Ь вЂ” п-1. й) Установить е — п„ь Пока $, э1 О, выполнять следующие действия: а) установить и < — 1,.
Если Ь„ф О, перейти к подшагу (с); Ь) установить Ь„~ — ж, ю ~ — и, аь ~- е, Ь ~ — Ь вЂ” 1. Завершить работу алгоритма, если В=О; с) установить с — п,. й1) Если ы ф 1, установить е ~- и, ю — Ьч и вернуться к шагу (й). В противном случае сообщить об ошибке: данный граф не является связным. В действительности работу алгоритма можно завершить, как только подшаг (Ь) сделает Ь равным 1, поскольку алгоритм 8 никогда не смотрит на начальное значение аэ. Однако мы можем продолжить работу и выполнить проверку связности графа.
93. Описанные далее шаги выполняют поиск в ширияу из и, проверяя, достижима ля вершина е без использованвя ребра е. Используется вспомогательный массив 61 ... 6„указателей на дуги, который должен быть инициализирован нулевыми значениями в конце шага 81; мы снова сбросим его значения к О...О. 1) Установить ге +- и и Ь, й) Установить | — и„ ь Пока су ~ О, выполнять следующие действия: а) установить е' 1- 17. Если 6'„ ф О, перейти к подшагу (д); Ь) если е' ф е, установить Ь,' е- е, Ь ~ — е', ю - е' и перейти к подшагу (и); с) если У ф е Ю 1, перейти к шагу (т); о) установить у — пу.
18) Установить и — 6„. Если и ф е, вернуться к шагу (й). сделано для ьиэвьилпГапаса,ого 7.2.1 ОТВЕТЫ К УПРАЖНЕНИЯМ 129 гк) Установить и — 1,. Пока и ~ и, устанавливать ю - Ь„, Ь„- О, и — ю. Перейти к шагу 89 (е — мост). г) Установить и — 1,, Пока и эь э, устанавливать ш — Ь, Ь„- О, и — и. Затем вновь установить и - 1, и продолжить выполненяе шага 88 (е — не мост). Перед началом описанных вычислений можно воспользоваться двумя быстрыми эвристиками. Если 8„= 1, то очевидно, что е является мостом; и если 1О ф О, то очевидно, что е мостом не является (поскольку существует другое ребро между и и е).
Этн частные случаи быстро обнаруживаются путем поиска в ширину; эксперименты автора показывают, что их использование определенно стбит затрачиваемых усилий. Например, проверка 1к обычно позволяет сэкономить около 3% общего времени вычислений. 96. (а) Пусть еь — дуга Ь вЂ” 1 — Ь.
Шаги, описанные в упражнении 94, устанавливают аь — е»+1 ь для и > Ь > 1. Тогда на уровне Ь мы сжимаем е» ь при 1 < Ь < и — 1. После посещения (единственного) остовного дерева е» 1... еэс», мы восстанавливаем е» ь и быстро обнаруживаем„что это мост, для и — 1 > й > 1. Таким образом, время работы линейно зависит от и; авторская реализация выполняет ровно 102а — 226 обращений к памяти при и ~ 3. Однако этот результат весьма существенно зависит от порядка ребер в начальном остовном дереве. Если на шаге 81 получается порядок "органных труб» наподобие е»/э+!с»/зе»/э+хе»/2-1 ° ° ° е»-1 ее в позициях аэ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
