Д. Кнут - Искусство программирования том 4 выпуск 4 - 2007 (1119377), страница 35
Текст из файла (страница 35)
[Я Бернулли (3. ВепюпП1) гючти сделал зто в Агв Согоес!аш)1, часть 2, глава 6.[ 14. АВС АВР АВЕ АСР АСЕ АСВ АОЕ АРВ АОС АЕВ АЕС АЕР ВСР ВСЕ ВСА ВРЕ ВОА ВОС ВЕА ВЕС ВЕР ВАС ВАР ВАЕ СРЕ СОА СРВ СЕА СЕВ СЕР САВ САР САЕ СВР СВЕ СВА РЕА РЕВ РЕС ОАВ РАС РАЕ РВС РВЕ РВА сделано для тагькичп(апаса.ого 142 ОТВЕТЫ К УПРАЖНЕНИЯМ 7.2.1 РСЕ РСА РСВ ЕАВ ЕАС ЕАР ЕВС ЕВР ЕВА ЕСР ЕСА ЕСВ ЕРА ЕРВ ЕРС. Это облексное упорядочение (см. алгоритм 7.2.1.3Н), циклически проходящее по еще не использованным буквам.
[Аналогичное упорядочение использовалось прн цостроении всех 120 перестановок пати букв в каббалистической работе %а'аг! ТЬедец, приписываемой Натану бен Саадьяху Харару (Хасан Ьеп Яа'ас(уаЬ Наг'аг) из Мессины, Сицилия, жившему в ХП1 веке; см. Ье Рогсе арейа С!пзг!х1а (М!!ап: Аде!рМ, 2001).) 15.
После у мы помещаем (п — 1)-сочетания с повторениями множества (у,..., гп), так что ответ — (! +' '„!+!" 0 ') = ( +„" 1 '). [Жан Воррель (деап Вогге!), известный также как Бутеонис (Вп1еоп1з), указал этот результат в своей книге Х.ой!зНса (Ьуоп, 1560) на с. 305-309. Он протабулировал все выбрасывания и костей для 1 < и < 4, а затем использовал суммирование по у, чтобы вывести, что есть всего 56+ 35+ 20+ 10 + 4+ 1 = 252 различных результата выбрасывания для и = 5 и 462 для п = 6.) 16.
1ч1. )Инициализация.) Установить г — и, 1 — 0 и ае — О. 7ч2. [Продвижение.) Пока г > и, устанавливать 1 ~- 1+ 1, а~ — д и г ~ — г — д, Затем, если г > О, установить Ф вЂ” 1+ 1 и а1 — г. МЗ. [Посещение.) Посетить композицию а~... аь 1ч4. )Поиск у.] Устанавливать у — Ь г — 1,...
до тех пор, пока не будет выполнено условие а !4 1. Завершить работу алгоритма, если у = О. г15. [Уменьшение аз.) Установить аз ~ — ау — 1, г — Ф вЂ” у' + 1, г —,у; вернуться к шагу Н2. 1 Напрямер, разбиениями для и = 7 и й = 3 являются 331, 322, 3211, 313, 3121, 3112, 31111, 232, 2311, 223, 2221, 2212, 22П1, 2131, 2122, 21211, 2113, 21121, 21112, 211111, 133, 1321, 1312, 13111„ 1231, 1222, 12211, 1213, 12121, 12112, 121111, 1132, 11311, 1123, 11221, 11212, 112111, 11131, 11122, 111211, 11113, 111121, 111112, 1111111. Сутры 79 и 80 Нараяны, по сути, описывают приведенную процедуру, но с обращеннымн строками (133, 223, 1123,...
), поскольку он предпочитал уменьшающийся солексный порядок. [Ранее Сарнгадева (багййабета) в Запййагагпакага (3 5, 316-375) детально разработал теорию для множества всех разбиений, которые могут быть образованы базовыми частями (1, 2, 4, 6).) 17. Количество $~„посещений равно ~~я+ ~ = Н [о"'ч) (см. упражнение 5.4.2- 7). Количество Х„выполнений проверки аз = 1 на шаге Ы4 удовлетворяет уравнению Х„= Х„~ + + Хв я+ 1, и мы находим, что Х„= ге + + $~„= = (ф'„+ (о — 1) Ъ'„~ + ° ° + Ъ'„ч+1 — 1)/(д — 1) = Н (Ъ'„). Количество 1'„установок а~ — д на шаге Х2 удовлетворяет тому же рекуррентному соотношению, и мы находим, что К„= Х„ч.
И наконец, условие г = 0 на шаге Ы2 выполняется К, „раз. 16. Если воспользоваться римскими цифрами, то 1666 записывается как МРС1 ХУ1, где М > Р > С > Ь > Х > У > 1. 19. Это строки 329 и 1022 (всего среди 1022 строф Путеануса данным свойством обладают 139).
20. Если 'гг!а' предшествует '1ппппа', существует 5! х 2! х (11, 12, 12,16) способов получить дактиль в (1,2,3,4)' й стопе соответственно. Если '1шшпа' предшествует сделано для жъивк! НГанаса.ого 7.2.1 ОТВЕТЫ К УПРАЖНЕНИЯМ 143 'сна', таких способов 5! х 2| х (16, 12, 12, 11). Таким образом, общее количество перестановок — 24480, (Лейбниц рассматривал эту задачу в конце своей Пмзег|апо с(е Агсе Со|пЬ|пасогйа и получил ответ 45 870; однако его аргументация переполнена ошибками.) 21.
(а) Ясно, что щюизводящая функция 1/((! — «и — уи«)(1 — «и — уиз)(1 — «со— — усе )) Равна С „л»о/(Р,д,т„,з,!)икеси|'«'у'. (Ь) Если 'Ф!Ь!' соответствует, а 1/!гйо' представляет собой — —, то общее количество равно 3(3!, умноженному на 2 ~, о(/(28 + 1,6 — 2!с,2;3,3) + /(2!с,б— — 2!с, 2; 2, 3)), те. 36((7 + 7) + (9 + 5) + (10 + 5) + (14 + 7)) = 2304. В противном случае '!!Ь!' соответствует —, 'У!гзяо' представляет собой —, а общее количество равно 2!3!, умноженному на ~,'„о(/(2/с,5 — 2!с,2; 3,2) + Д2(с,6 — 2л, 1; 3,2)), т.е.
12 ((7 + 6) + (5+ 4) + (4 + 4) + (О + 6)) = 432. (с) Пятая стопа начинается со второго слога 'сж)о', 'с!огеэ' или 'У!гйо'. Следовательно, дополнительное количество равно 3|3! 2 „о /(2!с, 5 — 2!с,2; 3,2) = 36(7+ + 5 + 4) = 576, и общее количество гекзаметров среди перестановок составляет 2304+ 432 + 576 = 3312. 22. Пусть а е (с!иос„эипс, соо), ~3 е (осе!о, с!осеэ, Упйо), |т = эйега и т = ПЪ|. Анализ Престета, по сути, эквивалентен анализу Бернулли, но он забыл включить 36 случаев ааатф3о(3. (В его защиту можно сказать, что зги случаи бесплодны с точки зрения поэзии; Путеанус не нашел им применения.) В издании 1675 года книги Престета опущены также все перестановки, заканчивающиеся на т)3.
Уоллис разделил все возможности на 23 типа: Т» О Тз О .. О Тзз. Он заявил, что типы 6 и 7 каждый дают по 324 строфы, однако в действительности !То( = !Тт! = = 252, поскольку его переменная | должна быть равна 7. а не 9. Кроме того, многие решения посчитаны им дважды: !Тз О Тз! = 252, (Тз О Тт! = !Тз О Тт! = !Тз О То! = = !То ОТ|о! = 36 и !Т|| ОТ|о! = !Тдз ОТ|з! = !Ты ОТ|с! = 12. Он пуопУстил 36 ваРиантов аддасгат|7 (19 из которых использовал Путеанус). Он также пропустил все перестановки из упражнения 21 (с); Путеанус использовал 250 нз их общего количества 576. В латинском издании книги Уоллиса, опубликованном в 1693 году, был исправлен ряд типографских ошибок, но не ошибки математические.
Уитворт и Хартли пропустили все случаи, когда 'с!Ь!'= — (см. упражнение 19) „ возможно потому, что количество людей, знающих классический гекзаметр, постоянно уменьшается. !Кстати, об ошибках: на самом деле Путеанус опубликовал только 1020, а не 1022 различных перестановок, поскольку строки 592 и 593 в его списке идентичны строкам 601 и 602. Однако у него не должно было возникнуть проблем с поиском еще двух гекзаметров — их можно получить, например, заменой '!ос эипг' на 'зипг со«' в строках 252, 345, 511, 548, 659, 663, 678, 693 или 797.) 23. Читая каждую диаграмму слева направо, так что 12 ~ 345 !)й!, получаем: П6 ПП! ПЮ ШП ШИ П6 й6 ПП! ПЮ ШП ПП! ПШ ПШ П1П ПИ! ЮП 66 ПП! 161 Шй )61 6П ФП ШП ЮИ ГйП РЭ Пй1 1Ю! !ПП 1Ш! ГйП !ПП 1ПП 1ПП ПШ В йШ 6! ШП 1ПП !й !61 ПШ 1пй ШП ПП! ШП 1В ИШ И1П ШИ сделано для ыг|уьулп(апаса.ого 144 ОТВЕТЫ К УПРАЖНЕНИЯМ 24.
Вот его правили для й = 0,1,...,п — 1 и для каждого сочетания 0 < 11 « < уь < и из и — 1 элементов по Й посещаем все разбиения (1,..., и — 1) ~ ( ум...,2ь) вместе с блоком (ум...,йю п). Для п = 5 получается следующий порядок: ПП1 ПП! 1ПП ВП П$П ПП1 ПП1 61 (П$1 В Пп1 ПП1 ПП1 ПП1 ПП! 1ПП П1П 1ПП ЮП (иП $1П$ ПП$1$й пй йП$ В ЙП 1пп й 6$ В В В В В!ПП ПП! 1ПП $Пп В В 1ПП $В В В В В В В В В В Однако, строго говоря, ответ к данному упражнению — "Нет", поскольку правило Хонды неполное, пока ие указан порядок сочетаний.
Он генерировал сочетания в солекснпм порядке (лексикографическом порядке ь...у1). Лексикографический порядок 11.../и также согласуется с приведенным списком для и = 4, но при этом Я В располагается перед Й)())(. Источник: Т. Наувв)п, Тойоли Масл.,у,, 33 (1931), 332-337. 25. Нет, в (28) отсутствует схема 14 ~ 235 (представляющая собой зеркальное отражение схемы 2 относительно горизонтальной оси). 26. Пусть а„— количество неприводимых разбиений (1,..., п), и пусть а„' — количество одновременно неприводимых и полных разбиений.
Эти последовательности начинаются с (амат,...) = (1,1,2,6,22,92,426,...) и (а',,а~ю...) = (0,1,1,3,9,33, 135,...). Ответом к данному упражнению является а'„— 1 для и > 2. Также оказывается, что а„является количеством симметричных полиномов степени и от некоммутирующнх переменных (см. М.С. %Ъ11, Вийе Масл. Х, 2 (1936), 626-637, где также протабулированы неприводимые разбиения на й частей.) Если А (х) = 2 „а„х" и В (г) = 2„„т„г" — неэкспоненцивльная генерирующан функция для чисел Белла, то А(х) В(х) = В(х) — 1; следовательно, А(х) = 1— — 1/В(х). Из результата упражнения 7.2,1,5-35 вытекает, что ~;„а'„х" = сА(х)/ /(1+ э — А(х)) = л(В(х) — 1)/(1+ гВ(х)). К сожалению, В(х) не имеет красивого аналитического вида, хотя и удовлетворяет интересному функциональному соотношению 1+ хВ(х) = В(г/(1+ г)). Заметим, что неприводнмые разбиения множества с п > 1 соответствуют "циклам колеблющейся диаграммы", в которых не имеется трех последовательных А, равных нулю (см.
упражнение 7.2.1.5-27). 27. Задача поставлена неоднозначно, поскольку нет точного определения диаграмм генджи-ко. Потребуем, чтобы все вертикальные линии одного блока имели одинаковую длину; при таком ограничении, например, разбиение 145)236 не имеет диаграммы генджн-ко с одним пересечением, поскольку диаграмма ФФ не разрешена. Количество разбиений без пересечений равно С„(см. упражнение 7.2.1.6 — 26). Для наличия одного пересечения элементы пересекающихся блоков должны находиться в ограниченно растущей последовательности хухры р~, х'9'+'хрь или ху~ ху~х' где 1,у,к,1> О.
Предположим, что мы рассматриваем шаблон х'ух~у~. Имеется 8 = 1+ 1+ к + 2 "слогов" между 1+ 1+ у + к элементами данного шаблона, н количество способов заполненняихнепересекающимисяразбиениямиравно',» „+, +Ь „, 1 «,СП - .С,. сделано для вълкпИапаса.ого ОТВЕТЫ К УПРАЖНЕНИЯМ 145 Это число можно выразить как и-а-1-ь-ы г о+у+в+2 [ 1С() (в-в-1-й-1)в согласно 7.2.1.6-(24). Суммирование по 6 дает С1„; щ„+Н; последующее суммиРоввние по ( и 1 Дает С1„-4Л~-зр Аналогично: два дРУгих шаблона дают вклад С1„вИ„+з1 и С~„вл„+4р Таким образом, общее количество разбиений с одним пересечением равно С~„з1<„+з) + + С1„48.+4р 28. Упорядочим делители сЬЬааа во количеству их простых сомножителей, а затем в солексикографическом порядке: 1 -< а ~ Ь -< с -( па -с 6а, < са < ЬЬ ~ сЬ < ааа < -с Ьаа -~ сап .< 6Ьа -с с6а -< сЬЬ < Ьааа -< сава -< 66аа -< сЬаа -< сЬ6п .< ЬЬааа -< -< с6ааа -< с66аа -с сЬЬаао.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
