Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 23
Текст из файла (страница 23)
[НМЯО[ Пусть | (р,о, г; э,1) — количество способов получить (ог, оч, о") путем конкатенации строк (з о 8 ° оо), где р+ о+ г = э+ 26 Например, г" (2,3 2; 3,2) = 5, поскольку этими пятью способами являются (о[о, о[оп, оо), (о[о, со[о, оо), (оо, о[о[о, оо), (оо, о[оо, о[о), (оо, оо[о, о[о). а) Покажите, что [иг ч г ю[1 У(р. ?,г з,1)— (1 — хи — из)(1 — ви — ов)(1 — гш — иД) Ь) Воспользуйтесь функцией 7" для подсчета перестановок (19), являющихся гекыметрами, при дополнительном условии, что пятая стопа не начинается посреди слова. с) Подсчитайте остальные случаи.
сделано для ьтьлилн$ана?а.ога 7.2.1 ГЕНЕРАЦИЯ ОСНОВНЫХ КОМБИНАТОРНЫХ ОБ'ЬЕКТОБ 97 ° 22. [М40[ Познакомьтесь с решениями задачи о количестве гекзаметров среди перестановок (19), опубликованными Престетом, Уоллисом, Уитвортом и Хартли. Какие ошибки они допустилн? 23. [80[ Какой порядок 52 диаграмм генджи-ко соответствует алгоритму 7.2.1.5Н? ~ 24. [83[ В начале 1800-х годов Тошиаки Хонда (Тов61аЫ Нопда) предложил рекурсивное правило для генерации всех разбиений (1,..., и).
Прн и = 4 его алгоритм давал такую последовательность разбиений: 1Ш ПП 1П! В ПП ПП ПП !1 й П[[ [Й[![н ПП йй ПП Можете ли вы сказать, какой будет последовательность при и = 5? Указание: см. формулу (26). 25. [15[ Автора изданной в ХУ1 веке книги ТЬе Агге ау ЕпяЬл6 Роев1е интересовали только "полные" в смысле упражнения 7.2.1.5-35 схемы рифм; другими словами, каждая строка должна рифмоваться, как минимум, с одной какой-то другой. Кроме того, схемы должны быть "неприводимы" в смысле упражнения 7.2.1.2 — 100: разбиение наподобие 12 [ 345 можно разделить иа двухстрочный стих, за которым следует трехстрочный. Наконец, схема не должна тривиально состоять из строк, которые рифмуются каждая с каждой. Является ли при этих условиях (28) полным списком пятнстрочных схем рифм? ° 26.
[НМ85] Сколько и-строчных схем рифм удовлетворяют ограничениям упражнения 25? ~ 27. [ФМ31[ Разбиение множества 14[25[36 может быть представлено диаграммой генджи-ко наподобие йй1[; однако каждая такая диаграмма для данного разбиения должна иметь, как минимум, трн места пересечения линий, а такие пересечения иногда рассматриваются как нежелательные. Сколько разбиений множества (1,..., и) имеют диаграммы генджи-ко, в которых линии пересекаются не более одного раза? ~ 28.
[25[ Пусть а„Ь и с — простые числа. Джон Уоллис (Зппп %а18э) перечислил все возможные разложения азЬзс следующим образом: сЬЬааа, сЬЬаа а,Ьсааа ° Ь, 66ааа с, с66а аа, сЬЬа . а а, с6аа Ьа, сЬаа Ь. а, 66аа са, 66аа с а, сааа . ЬЬ, сааа Ь Ь, Ьааа ° сЬ, Ьааа ° с ° 6, сЬ6 ааа, сЬ6 аа а, сЬЬ ° а а ° а, сЬа Ьаа, сЬа 6а а, сЬа ° аа Ь, сЬа Ь а а, ЬЬа саа, 66а са а, ЬЬа аа с, ЬЬа с а а, саа ЬЬ а, саа Ьа Ь, саа Ь Ь а, Ьаа сЬ а, Ьаа са Ь, Ьаа Ьа с, Ьаа с 6 а, ааа сЬ Ь, ааа ЬЬ.с, ааа с Ь Ь, сЬ Ьа.аа, сЬ 6а а ° а, с6 ° аа ° Ь а, сЬ Ь.а а ° а, 6Ь.са аа, ЬЬ ° са ° а а, ЬЬ.аа с а, 6Ь с а а а, са Ьа ° Ьа, са ° Ьа Ь а, са ° аа Ь Ь, са ° Ь.Ь а ° а, Ьа ° 6а с ° а, Ьа ° аа ° с Ь, Ьа с Ь а а, аа с Ь Ь ° а, с ° 6.
6 а а ° а. Какой алгоритм использовал Уоллис для генерации разложения в данном порядке? ~ 29. [84[ В каком порядке Уоллис (%аПЬ) сгенерировал бы все разложения числа аЬс0е = 5 ° 7 11 13 ° 17? Ваш ответ должен представлять собой последовательность диаграмм гянджи-ко. 30. [М80[ Чему равен коэффициент а1ча~~'...з~+" в (аох+а1хз+а хз+ ) ? (См.
формулу (29).) сделано для вью! БГанасн.огя 98 КОМБИНАТОРНЫЙ ПОИСК 31. (20) Сравиите упорядочеиия разбиений (30) де Муавра (бе Мо|гге) и (31) де Мои- морта (бе Мопггпогг) с алгоритмом 7.2.1,4Р. 32. (211 (Р.Й. Бошкович (Н.1. ВоегхичсЬ), 1Т43.) Перечислите все разбиения 20, у которых все части представляют собой 1, Т или 10.
Разработайте алгоритм для перечисления всех таких разбиеиий зедаииого целого числа и > О. сделано для вхехилпГапаса.ого Ответы к упражнениям Раздел 7.2.1.6 1. Он может "видеть" левую скобку слева от каждого внутреннего узла, а правую— снизу от каждого внутреннего узла. Можно также связать правые скобки со встречающимися внешними узлами, кроме самого последнего П (см. упражнение 20). 2. Е1. (Инициализация ) Установить гь - 2к-1 для 0 < и < и (считаем, что и > 2).
Е2. (Посещение.) Посетить сочетание х|гз... х„. Е3. (Простой случай?) Если з„1 < в„— 1, установить х„— г„— 1 и вернуться к Е2. Е4. (Поиск Д Установить у — и-1 и з„- 2п — 1. Пока ву ( = г — 1, устанавливать ху ~ — 2у — 1 и у ~-,у — 1. Еб. (Уменьшение г„.) Завершить работу алгоритма, если у = 1. В противном случае установить ву — х — 1 и вернуться к шагу Е2.
! 3. Пометим узлы дерева в прямом порядке обхода, Первые гь — 1 элементов а(... аз„ содержат Й-1 левых скобок н хь -Й правых скобок. Таким образом, имеется избыток 2Й вЂ” 1 — хь левых скобок по сравнению с правыми, когда червь впервые достигает узла Й, а 2Й вЂ” 1 — вь представляет собой уровень (или глубину) этого узла. Пустыу~... д„— инверсия р|... р„, так что узел й представляет собой дь-й узел в обратном порядке обхода.
Поскольку и находится слева от у в р~... р„тогда и только тогда, когДа вь < 9~, мы видим, что сь — количество Узлов У', пРеДшествУюЩих Й в прямом порядке обхода, но следующих за ним в обратном порядке, т.е. количество предков к; это вновь дает нам уровень к. Альшлрнашнвнвв докввашавьство. Можно также показать, что обе последовательности — зг...
г„н сг... с„— обладают, по сути, одной и той же рекурсивной структурой (5): Яг, = (Я„( 0+1г),1(Я(р си+ 1г ~) при 0 < р < ((, а С, = С„( гп (д — Р) С( Ою (РассмотРите паРы к последней, пРедпоследней и тд. ле. вым скобкам.) Кстати, формула 'се+1+ 4, = сь + 1" эквивалентна (11). 4. Почти истинно; просто строки Нг...И„и дг...з„находятся в рбмваюн(ам порядке, в то время как строки р(...р„и с|...
с„— в возрастающем. (Это лексико- графическое свойство для последовательности перестановок р1 ...р„не наследуется автоматически из лексикографического порядка соответствующих таблиц инверсий с1... с„; этот результат выполняется для данного конкретного класса рг... р„.) 5 4 бы=020020010320104' вг...хш = 1 2 5 6 7 10 11 12 14 15 19 22 23 25 26„ р1...ры = 2 1 5 4 8 10 9 7 11 6 13 15 14 12 3: с1...сш =О 1 О 1 2 1 2 3 3 4 2 1 2 2 3. 6.
Скобки связаны друг с другом, как обычно; мы просто искривляем строку и замыкаем ее в кольцо так, что аз„становится соседним с аы и замечаем, что разница между левыми и правыми скобками может быть восстановлена из контекста, Если а( соответствует низу окружности„как в табл. 1, мы получим показанную диаграмму. сделано для ьньньнда$апаса.ого у.гл 100 ОтнвтЫ К УПРАЖНЕНИЯМ (А. Эррера (А.
Еггега), Мйто1гез де )а С!аюе Ясй 8', Асад. Воув1е де Веющие, (2) 11, 6 (1931), 26 рр.) т. (а) Она равна ) ) О О; присваивание ад - 'С восстановит начальное состояние строки. (Ь) Будет восстановлено исходное бинарное дерево (из шага В1), за исключением того, что („= и + 1. 8. 11 ° .1ш = 2 0 4 5 0 7 8 0 10 О О 13 0 15 0~ г1...гш = 3 О 0 6 0 12 11 9 0 О О О 14 0 0; е1...еш = 1 О 3 1 0 2 2 0 1 О 0 2 0 1 О; е1...еш = 1 0 12 1 0 5 3 О 1 О 0 3 О 1 О. 9. Узел у является предком узла л тогда и только тогда, когда еу + у > й. (Квк следствие, получаем с1 + " +с„ = «1 + + в„.) 10.
Если у — ицпекс ть Й-й левой скобки, то и~у = сь + 1 и ю' = сы где 7 — яндекс соответствующей правой скобки. 11. Обменяйте левые и правые скобки в ат„... а| для получения зеркального изображения а1... ат„. 12. Зеркальное отображение (4) соответствует лесу однако суть транспонирования станет более очевидна, если изобразить связи с правым братом н левым потомком горизонтально и вертикально, а затем выполнить транспонирование получившейся матрицы. сделано для ткьктнл~ГанаМ.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 101 7.2.1 13.
(а) По иидукции по количеству узлов можно получить ргеогг1ег (г' ) = ровгогг1ег(г') и роэсогг(ег (В ) = ргеогггег(г') (Ъ) Пусть Е соответствует бииариому дереву В, Тогда, как упомииалось после 2.3.2-(6), ргеогг(ег(Е) = ргеоп1ег(В) и роэсогбег(гг) = 1поп$ег(В). Поэтому ргеогггег (Гт) = ргеогг(ег (В") = розсоп(ег (В) ие имеет простой связи с ргеоп(ег (Р) или роесогг)ег (г'). Но розсогг)ег (г т) = шоп1ег (Вл) = 1погг(ег (В) = ровгоп(ег (г') 14. Согласно ответу к упражнению 13, роэФогг)ег (г лт) = ргеогг(ег (г') = ргеогггег (В) где Г естествеииым путем соответствует В; в свою очередь, роэсогс)ег(г'™) = ргеоп1ег (г т) = роемггг(ег (В).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
