AOP_Tom3 (1021738), страница 164
Текст из файла (страница 164)
Просмотрим теперь Г, С, и Н и сформируем два новых файла Г' и С' следующим образом. Если текущие записи файлов Г, С, Н равны соответственно (х, х'), (у, у'), (ш х'), то: !) если т' = х, выведем (т, «') в Г' и перейдем дальше в файлах Г и Н: й) если х' = у~, выведем (у-г, х) в С~ и перейдем дальше в файлах Г и С; ш) если х > у', перейдем дальше в файле С; !г) если г > х, перейдем дальше в файле Н. Когда дойдем до конца файла Г, рассортируем С~ по вторым компонентам и сольем с ним С; затем заменим Г на 2й Г на Г', С на С'.
Таким образом, Г принимает значения 2, 4, б,...; при фиксированном Г для сортировки необходимо выполнить О(!обЖ) проходов. Следовательно, общее число проходов будет О((!ой )т) ). В конце концов выпалнится 1 > )э' и файл Г опустеет; тогда останется только рассортировать С по первым компонентам. 26. (Идея решения принадлежит Д. Шанксу (О. ЯЬап)ге).) Подготовьте два файла, один из которых содержит числа а "спойр, а другой — Ьа "шос) р, 0 < и < т. Рассортируйте оба файла и найдите общий элемент. Замечание. В результате время выполнения 8(р) в худшем случае сократится до б!(ьгр !ок р). Возл~ожно и дальнейшее повышение производительности; например, несложно за !окр шагов проанализировать, является ли и четным, проверив, какое нз равенств ЬШ П7э шоб р = 1 и (р — 1) имеет место. В общем случае, если 7' является любым делителем р — 1, а с! — любым дшсителем йсс)(/, л), можно аналогичным образом найти (гс/4) шос) /, отыскав значение ьш 'сс с в таблице длиной //с), если простыми делителями р — 1 являются Ос < Оэ « Ос, причем, если 9с — мало, можно быстро вычислить л, выполняя поиск разрядов справа налево в представлении со смешанными основаниями дс,, 9,.
(Эта идея принадлежит Р. Л. Сильверу (В.. П 8!!чег), 1964; см. также Я. С. РоЫ!8, М. Не!!шап, 7ЕЕЕ ТгалэасВолэ 1Т-24 (1978), 106-110.) Джон М Поллард (Лаба М. Ро!!шс)) нашел давольно элегантный способ вьсчисвения дискретных логарифмов, требующий порядка 0(ь/р ) операций шос! р при малых затратах памяти.
Способ основан на теории случайных отображений (гапс1опс шарр!пба). См. МагЛ. Сотр. 32 (1978), 918-924, где он предложил еще один метод, базирующийся на числах лз = гэ шоЙ р, которые имеют только малые простые делители. Асимптотически более быстрые методы обсуждаются в ответе к упр. 4.5.4-46. РАЗДЕЛ 5.1.1 1. 205223000, 27354186. 2.
Ьс = (т — 1) шоб л; Ь!тс = (Ь, + т — 1) шос! (л — 1). 3. а = ап~.с ! ("отраженная" перестановка). Этуидею использовал О. Теркем (О. Тегс!иеш) [зоагл, с!е МасЛ, 3 (1838), 559-560) для доказательства того, что среднее число инверсий в случайной перестановке равно э [э). 4. С1. Установить хо с — О. (Если возможно, желательно на погледуюгцих циклах, когда 1 < 1 < л, использовать для х ту же память, что и для Ь .) С2. При Л = л, л-1,..., 1 (именно в этом порядке) выполнить следующее; установить 1 с- О, затем ровно Ьс, раз установить ! с- х;, затем ус~влазить хь с — х и х, с- )с.
С3. Установить ! с — О. С4. При Л = 1.2... и (именно в этом порядке) выполнить следующее; установить аь с- х„, затем установить у с- х,. 1 В упр. 5.2-12 показано, как экономно использовать памить. 5. Пусть а — цепочка упорядоченных пар целых неотрицательных чисел [т.,лс)..
[ты ль]; обозначим через ]а( = й длину цепочки а, а через с -- пустую (длиной 0) цепочку. Рассмотрим двоичную операцию о, рекурсивно определенную на парах таких цепочек следующим образом: сон=нос=а; [т, л](а о ([т' — т,л'])!)), если т < т', ([гл, л]а) а ([т', л')А) = [т', л') (([т-гл' — 1, л]а) о !7), если гл > т'. Из такого определения операции глелуат, что время, необходимое дпя вычисления а а /1, пропорционально (а о 17( = (а( + (3(. Более того, можно показать, что операция о ассоциативна и что [Ьм1] о [Ьм2] о о [Ь,л] = [О,ас][О,аэ] .. (О,а„]. Выражение в левой части можно вычислить за [!8 л'] проходов, комбинируя на каждом из них пары в цепочках, т.
е. всего за 0(л!об л) шагов Пример. Начав с (2), зададимся целью вычислить (2, !) о [3, 2] а [6,3] о [4,4] о [О, 5] о [2,6] о [2, 7] о [1,8) о [0,9]. После первого прохода зто выражение преобразуется и [2, 1Ц1, 2( а (4, 4][1, 3] о [О, 5] [2, 6] о [1, 8ЦО, 7] о [О, 9]. Второй проход преобразует его в [2, 1] [1, 2] [1, 4Ц1, 3] о [О, 5)[1, 8ЦО, 6)[0, 7] о [О, 9). Третий проход приведет к [О, 5Ц1, 1ЦО, 8)[0, 2ЦО, 6][О, 4ЦО, 7)[0, 3] о [О, 9].
После четвертого прохода получилс (1). Обоснование. Цепочка наподобие [4,4Ц1,3] представляет "аааа4а3а ", где "а" означает пропуск; операция а о су вставляет пропуски и заполнения из с7 на место пропусков в а. Обратите внимание, что, в отличие от упр. 2, получен алгоритм решения задачи Иосифа, который требует времени, пропорционального 0(п !об и), вместо 0(глп). Таким образом, мы частично ответили на вопрос, поставленный в упр. 1.3.2-22. Другое решение этой задачи (0(п !об и), которое потребует только оперативной памяти), очевидно, следует из методики сбалансированного дерева. 6. Начать с Ь1 = Ьэ = = Ь„= О. При Л = [!8п), [!8п!'-1,...,О выполнить следующее. установить х, е- 0 для О < е < п/2ьг', затем для 1 = 1,2,...,п установить г е- [а,/2"! шод 2, э е- [а /2ь ы! (это, по существу, выделение отдельных разрядов); если г = О, установить Ь„,.
е- Ь з + вм а если г = 1, установить х, +- х, + 1. Другое решение будет продемонстрировано в упр, 5.2.4-21. 7. Вз < у и Сз < и — 1. поскольку а! имеет У вЂ” 1 элементов слева от него и и — з элементов справа. Для того чтобы восстановить а~ аэ... а„по В| Вэ... В„, начните с элемента 1; затем для Л = 2,., и добавляйте по 1 к каждому элементу, большему или равному Л вЂ” Вю н справа приписывайте элементы Л вЂ” Вь (см.
метод 2 в разделе 1.2.5). Аналогичная процедура годится и для таблицы Сы Альтернативный метод предполагает использование результатов следующего упражнения. [Таблица инверсий сь была рассмотрена Родригесом (В. О. Нобг!8пез) в у. с(е МаГЛ. 4 (1839), 236-240; впервые таблица инверсий Сь появилась в книге Нессо ЛеЛгЬисЛ с(ег СошЬ!лагос!9 (1901), 55.[ 8. Ь' = С, с' = В, В' = с, С' = Ь, поэтому каждой инверсии (апас) таблицы аю., а„ соотвотствует инверсия ( ) !) перестановки а',... а'„. Справедливы и другие соотношения: (а) сз = 1 — 1 тогда и только тогда, когда (6< > Ьз для всех ! < 1); (Ь) 6э = и — 1 тогда и только тогда, когда (с, > сэ для всех Г > у); (с) 6, = 0 тогда и только тогда, когда (с; — 1 < с, - у для всех ! > 1); (О) с = 0 тогда и только тогда, когда (Ь, + Г < 6 + 1 для всех ~ < 2); (е) 6; < Ьсе1 тогда и только тогда, когда а[ < аг ы и с, > сьы, (Г) а, =,1 + Сз — В;; а', =1+6, — с .
9. Равенство Ьь = Сь = Ьг~ эквивалентно равенству аь = ав 10. ~/ГО. (Один из способов ввести гистему координат для усеченного октаздра — поставить в соответствие взаимным обменам соседних элементов 21, 43, 41, 31, 42, 32 векторы (1,0,0), (О, 1, 0), э(1, 1, ь'2), -'(1 -1, ь/2), 1( — 1, 1, ~/2), 1(-1, — 1. ь/2). Сумма этих векторов равна (1, 1, 2./2) и представляет собой разность между вершинами 4321 и 1234.) Существует решение, имеющее более симметричный вид — представить вершину я в четырехмерном пространстве следующим образом: (е — е [ (и, о) инверсия перестановки я), где е~ = (1,0,0,0), еэ = (0,1,0,0), ез = (0,0,1,0), е4 = (0,0,0,1). Таким образом, 1234 еэ (0,0,0,0); 1243 еэ (0,0,— 1,1); ...; 4321++ ( — 3,— 1,1,3).
Все точки лежат на трехмерном подпространстве ((ю, х, у, х) [ ш+ х + у Г в = 0); расстояние между соседними вершинами равно ~/2. Так же (см. ответ 8, (Г)) можно представить я = а1 аэ аз аэ вектором (а(, аэ, аз, а4), где а', аэ аз а1 — обратная перестановка. (Такое 4-0 представление усеченного октаэдра перестановками в качестве координат было рассмотрено вместе с обобщением на и-мерное пространство С. Говардом Хинтоном (С. Ноиагб Н!пгоп) в книге ТЛе РоигГЛ Випепсйоп (мопс(оп, 1904), глава 10, Много лет спустя другие свойства были найдены Гилбодом (Сп!!Ьапй) и Розентилем (Ноеепег!еЫ), которые назвали объект, изображеннмй на рис.
1, пермутаэдром (регпшгаЬебгоп); гм. упр. 12.) Копии усеченного актаэдра заполняют трехмерное пространство способом, который принято называть простейшим [см. Н. Иге!пЬапэ, Ма!Леша!!са( ЯпвреЛогз (ОхГогс), 1960), 200-203; С. Я. ЯппсЬ, Яс!епс!Ос Агпепсал 190, 1 (Лапласу, 1954), 58-64]. В книге У из Со!!есг(оп Паппюса (300 г. н, э.) усеченный октвздр упоминается как одно из тринадцати особых тел, исследованных Архимедом. Примером архимедова тела является непризматический многогранник, любая вершина которого симметрична по отношению к любой другой, а любая грань является правильным многоугольником, но не все они идентичны Его можно найти, например, в книге 1гг.
Чг. Воияе Вай, Мазйетайса! Несгеаиопя ялг! Еззауя, гег!яег) Ьу Н. Б. М. Сахесег (Масппйап, 1939), глава 5, или Н. Магсуп Сипг1у, А. Р. ВоПесс Масйешасгса! Могсе!я (ОхЕоггс, 1952), 94 — 109. 11. (а) Очевидно. (Ь) Постройте ориентисзованный граф с вершинами (1, 2,..., п) и дугами х -+ у, если либо х > у и (х, у) б Е, либо х < у н (у,х) б Е. Если этот граф не содержит ориентированных циклов, его вершины можно топологически рассортировать; полученное линейное упорядочение и есть требуемая перестановка. Если же ориентированные циклы присутствуют, то длина кратчайшего из них равна 3, потому что не бывает циклов длиной 1 или 2 и потому что более длинный цикл аг -з аз -+ аз -г аз -+ — з аг можно сократить (либо аг -г аз, либо аз — з аг). Но ориентированный цикл длиной 3 содержит две дуги либо из Е, либо из Е, и, таким образом, доказано, что либо Е, либо Е не транзитивно.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
