Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 62
Текст из файла (страница 62)
2, Ь! = (т — 1) шог( и„'Ьрчп = (Ьр + т — 1) шоб (и - Я. 3. пр — — о„ар р ("отражеииая" перестановка). Эту идею использовал О. Теркем (О. Тещиеш) [аопгл, р(е Магй. 3 (1838), 559-560] для доказательства того, что среднее число инверсий в сэучайиой перестановке равно -' ["). 4. С1. Устаиовить ха +- О. (Если возможно, желательно иа последующих циклах, когда 1 < у < и, использовать для яр ту же памить, что и для Ь .) С2.
При Ь = и, п-1,..., 1 (именио в этом порядке) выполнить сэеррующее; установить р а- О, затем ровно Ьь раз установить у <- я, затем установить хэ !- х и х а- Ь. СЗ. Устаиовить у <- О. С4. При Ь и 1, 2,..., и (имеиио в этом порядке) выполнить слеррующее: установить оь +- хр, затем установить у а- хр, $ В упр. 5.2-12 показано, как экономно использовать память. б. Пусть и — цепочка упорядоченных пар целых неотрицательных чисел [тр, ир]... [ть,тм]; обозначим через ]о[ = Ь длину цепочки и, а через с — пустую (длиной О) цепочку.
Рассмотрим двоичную операцию а, рекурсивно определенную иа парах таких цепочек следующим образом: сап=пас=а; [т,и](оа ([т'-т,и']ру)), если ри < т', ([рп, и]п) а ([т',и)6) = [ри',и](([т-т' — 1,и)п) а 8), если ри ) ри'. Из такого определения операции следует, что время, необходимое для вычисления па р7, пропорционально [и а 6[ = [а] + ]ру]. Более того, можно показать, что операция а асоэциативпа и что [Ьр, Ц а [Ьм 2] а а [Ь,и] = [О орЦО пэ)... [О о ).
Выражение в левой части можво вычислить за [!8 и] проходов, комбинируя иа каждом из иих пары в цепочках, т. е, всего за 0(и!оби) шагов. 77ример. Начав с (2), зададимся целью вычислить [2, Ц а [3, 2] а [6, 3] а [4, 4] а [О, 5) а [2, 6! а [2, 7) а [1„8) а [О, 9]. После первого прохода это выражение преобразуется в [2, 1Ц1, 2] а [4, 4Ц1, 3) а [О, 5)[2,6] а [1, 8ЦО, 7) а [0,9).
Второй проход преобразует его и [2, 1Ц1, 2Ц1, 4Ц1, 3) а [0,5Ц1,8Ц0,6Ц0,7) а[0,9]. Третий проход приведет к [0,5Ц1,1ЦО,ЗЦО,2Ц0,6ЦО,4Ц0,7ЦО,З] а [О, 9], После четвертого прохода получим (1). Обасиаеоиие. Цепочка наподобие[4,4Ц!,3] предстаалиет "оо„„4оЗо ", где '"„" означает пропуск; операция а а р9 вставляет пропуски и заполнения из ру иа место пропусков в и, Обратите виимаиие, что, в отличие от упр. 2, получек алгоритм решения задачи Иосифа, который требует времени, пропорционального О(п!об»»), вместо 0(шп).
Таким образом, мы частично ответили на вопрос, поставлеииый в упр. 1.3.2-22. Другое решение этой задачи (0(п 1об и), которое потребует только оперативной памяти), очевидно, слезет из методики сбалансированного дерева. 6. Начать с Ь| = Ь» = ° = Ь„= О. При Ь = (!йп),(!8п)-1,...,0 выполнить следующее: усталовить я, »- 0 для 0 < э < и/2"+', затем для у = 1,2,...,п установить г»- (а»/2») шо»! 2, »»- (а /2»»') (это, по существу, выделение отдельных разрядов); если г = О, установить Ь„, »- Ь,, + я„,а если г = 1, устаиовить х, »- я, + 1.
Другое решение будет продемонстрировано в упр. 5.2.4-21. 7. В, < / и С» < и -у, поскольку а! имеет / — 1 элементов слева от него и и -у элементов справа. Для того чтобы восстановить а~ а»... а„по В» Вг... В, начните с элемента 1; затем для Ь = 2,...,и добавляйте по 1 к каждому элементу, большему или равиому Ь вЂ” В», и справа приписывайте элементы Ь- В» (см, метод 2 в разделе 1.2.5). Аиалогичиая процелура годится и для таблицы С». Альтернативный метод предполагает использовалие результатов следующего упражнения. (Таблица ииверсий с» была рассмотрена Родригесом (В. О. Йо»!г!8пея) в Х»!е Ма»Ь. 4 (1839), 236-240; впервые таблица инверсий С» появилась в книге Хе»»о йейгбисЬ»(ег СотЬша»оНЬ (1901), $5.) 8. Ь' = С, с' = В, В' = с, С' = Ь, поэтому каждой инверсии (опе.) таблицы о~...
о„ соответствует инверсия (у, ») перестановки а',... а„'. Справедливы и другие соотношеиия: (а) с> — — / — 1 тогда и только тогда, когда (Ь; > Ь» для всех» < /); (Ъ) Ь! = л — / тогда и только тогда, когда (с, > с» для всех» > у); (с) Ь» = 0 тогда и только тогда, когда (с; — » < с» —,! для всех» > у); (о) с» = 0 тогда и только тогда, когда (Ь;+» < Ь»+/ для всех » < /); (е) Ь; < Ь»ь» тогда и только тогда, когда а,' < а; '»» и с» > с»»ы (Е) а» =,1 + С, — В;; а~ — — )+Ь! -с~. 9. Равенство Ь» = С» ж Ь~» эквивалентно равенству а» = а» 10.
»/ГО. (Опии из способов ввести систему координат для усеченного октаэдра — поставить в соответствие взаимным обменам соседних ююмеитов 21, 43, 41, 31, 42, 32 векторы (1,0,0), (0,1,0), »(1,1, ~/2), »(1,-1,»/2), »1(-1,1, »/2), »»(-1,— 1, Л). Сумма этих векторов равна (1, 1,2»/2) и представляет собой разиость между вершинами 4321 и 1234.) Существует решение, имеющее более симметричный вид — представить вершину я в чсгемрсхмерном пространстве следующим образом: (е„ вЂ” е )(и,е) инверсия перестановки я), где е~ = (1,0,0,0), е» (0,1,0,0), еэ = (0,0,1,0), е» = (0,0,0,1). Таким образом, 1234+» (0,0,0,0); 1243»» (0,0,— 1,1); ...; 4321+» (-3,-1,1,3). Все точки лежат на трехмерном подпростраистве ((ю, з, у, ») ( ш+ я + у+» = О), расстояние между соседними вершинами равно»/2. Так же (см.
ответ 8, (Е)) можно представить я = ад а» а» а» вектором (а'„а», а», а»), где а'~ ໠໠໠— обратная перестановка. (Такое 4-!3 представление усеченного октаэдра перестановками в качестве координат было рассмотрена вместе с обобщением иа и-мерпое пространство С. Говардом Хиитоиом (С. Нопаг»! Нш»оп) в книге ТЬе Ропг»Ь В!шел»!оп (Еопдоп, 1904), глава 10. Много лет спустя другие свойства были найдены Гилбодом (Сш!Ъапд) и Розеитилем (Коэепэ»!еЫ), которые назвали объект, изображенный иа рис. 1, пермутвэдром (регшп»аЪебгоп); см. упр, 12,) Копии усечениого октаэдра заполняют трехмерное пространство способом, который принято называть простейшим (см.
Е!. Б»е!пЪапэ, Масйел»аиса! Яларэйош (Ох(ог»1, 1960), 200-203; С. Я. Бпи»Ь, Яс!еп»!бс Ашег!сап 190, 1 (Лапласу, 1954), 58-84). В книге Ъ' из Со!!есНол Паппюса (300 г. н, э.) усеченный октаздр упомииается как одно из трииадцати особых тел, исследованных Архимедом. Примером архимедова тела является непризматический многогранник, любая вершина которого симметрична по отношению к любой другой, а любая грань является правильнмм многоугольником, но не все онн идентичны.
Его можно найти, например, в книге %'. %. Конзе ВаИ, Магйешабса! Еесхеаг!опз апд Еарауз, гегдзед Ьу Н. 8. М. Сохесег (Масшй!ап, 1939), глава 5, или Н. Ма»туп Спиду, А. Р. КоИем Магйепгабсй Модей (Ох6ж1, 1952), 94-199. 11. (а) Очевидно. (Ь) Постройте ориентированный граф с вершинами (1, 2,..., и) и дугами х -» у, если либо х > ун (х,у) б Е, либо х < уи (у,х) б Е. Если этот граф не содержит ориентированных циклов, его вершины можно топологичсски рассортировать; полученное линейное упорядочение и есть требуемая перестановка, Если же ориентированные циклы присутствуют, то длина кратчагппего из них равна 3, потому что не бывает циклов длиной 1 или 2 и потому что более длинный цикл аг -+ аэ -+ аз -+ ар -р .
-р аг можно сократить (либо а г -р аз, либо аз -г аг ). Но ориентированный цикл длиной 3 содержит две луги либо из Е, либо из Е, и, таким образом, доказано, что либо Е, либо Е не транзнтнвно. 13. (С. Т. СпИЬапд, Р. Впвепяс!еЫ, Ма»Ь. ег Яс!епсар Нигпа!пеэ 4 (1963), 9-33.) Предположим, что (а,Ь) б Е, (Ь,с) б Е, (а,с) д Е.
Тогда при некотором й > 1 имеем а = хо > хг » х» = с, где (хах;+г) б Е(ггг) 0 Е(эг) при О < г < Ь. Рассмотрим следующий контрпример при минимачьном Ь. Поскольку (а, Ь) 1г Е(лг) и (Ь,с) й Е(ггг), то (а,с) д Е(ггг); аналогично (а,с) 8 Е(яэ); саедовательно, Ь > 1. Но если хг > Ь, то (х,,Ь) б Е противоречило бы лгинимальности Ь, а из того, что (хг, Ь) б Е, следовало бы (а Ь) б Е.
Аналогично если хг < Ь, получится что и (Ь хг) 6 Е и (Ь хг) б Е невозможны. 13. Для любого фиксированного выбора Ьг,...,Ь, г,Ь .~г,...,Ь в таблице шгверсий в сумме ) „,. Ь, предполагается, что каждый остаток цо модулю гп встречается точно один раз по мере того, как Ь пробегает все возможные значения О, 1,, гп — 1. 14. Конструкция, предложенная в указании, переводит пары разбиений на различные части одно в другое во всех случаях, кроме двух: У Ь = р» и д = Ь = р» — 1.
В этих особых случаях и равно соответственно(27'-1)+ +! = (37' — у)/2 и (22)+ +(2+1) = (Зг +!)/2 и существует единственное непарное разбиение на д частей. (Первоначальное доказательство Эйлера в )г!ог! Сошшепк Асад. Яа. Рег. б (1754), 75-83, также очень интересно. С помощью простых преобразований он показал, что бесконечное произведение равно эг, если мы определим э„в виде степенного ряда 1 — х~" ' — х~" 'э +г для и > 1. Конечная версия бесконечной эйлеровой суммы рассмотрена Кнутом и Патергоиом (Расегэоп) в ЕЗЬопасс! 4)п те4У 18 (1978), 198-212.) 16. Транспонируйте точечную диаграмму с тем, чтобы перейти от р к Р, Производящая функция для Р получается довольно легко,так как сначала можно выбрать любое число единиц (производящая функция 1/(1 — х)), затем независимо выбрать любое число двоек (производящая функция 1/(1 — зг)), ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
