AOP_Tom1 (1021736), страница 48
Текст из файла (страница 48)
1 Строки 64 — 68, в которых строится циклическая запись на основании таблицы Т и таблицы имен, представляют собой небольшой алгоритм, который заслуживает внимания. Величины А, В, ..., В, 5, Т, И', Е, влияющие на время выполнения программы, конечно, отличаются от одноименных величин, которые использовались при анализе программы А. Анализ этих величин будет интересным упражнением для читателя [см. упр. 10). Опыт показывает, что основная часть времени выполнения программы В будет потрачена на поиск в таблице имен: это время определяется параметром Ь'. Существуют более эффективные алгоритмы поиска и построения словарей имен; они называются алгоритмами тлаблиц символов и играют важную роль в прикладной математике.
В главе 6 мы займемся всесторонним исследованием эффективных алгоритмов таблиц символов. Обратные перестановки. Обратная перестановка х для перестановки х — это такая перестановка, которая отменяет действие х; если в х элемент 1 переходит в 5 х, то в х элемент 7 переходит в 1.
Таким образом, произведение ях равняется тождественной перестановке; то же самое справедливо и для произведения х х. Обратную перестановку часто обозначают через;г ~, а не я, но верхний индекс 1 явно лишний (по той же причине, по которой х~ = х). Каждая перестановка имеет обратную. Например, обратной перестановкой для сну Ьеа аЬсйеу ~даЬес Рассмотрим некоторые простые алгоритмы вычисления обратной перестановки. Предположим, что в оставшейся части раздела мы будем иметь дело с перестановками чисел [1,2,..., и).
Если Х[Ц Х[2]... Л [и] — такая перестановка, то существует простой метод вычисления перестановки, обратной к ней. Присвоим У[Х[1с]] 4 /с для 1 < Ь < и. Тогда У[Ц У[2]... 1'[и] — искомая обратная перестановка. В этом методе используется 2п ячеек памяти, а именно — п для Х и и для Е А теперь ради интереса предположим, что и очень велико, в то время как нужно вычислить обратную перестановку к Х[Ц Х[2]... Х[п], не используя слишком много дополнительного пространства памяти. Необходимо вычислить обратную перестановку "на месте", чтобы после окончания работы алгоритма массив Л [Ц Х[2]...
Х [и] представлял собой перестановку, обратную к первоначальной. Простое присвоение Л [Х[Ь]] < — А для 1 < Ь < и в этом случае, разумеется, не пройдет, но, рассматривая циклическую структуру, можно получить следующий простой алгоритм. Таблица 3 ОБРАЩЕНИЕ ПЕРЕСТАНОВКИ 621543 С ПОМОЩЬЮ АЛГОРИТМА 1 «3 13 6 — 3 2 2 — 6 — б 5 5 4 4 — 1 -1 1 6 — 3 б — 1 1ц 15 — 3 3 2 2 б б ц 5 4 4 1 1 2 1 — 2 — 2 — 2 — 3 После шага 15Н 12 — 3 — 3 2 2 — б — б 5 5 4 4 1 1 б 5 — 1 — 1 — 1 4 12 13 б б 2 2 1 1 5 5 4 4 3 — 1 б 3 — 1 — 6 3 1 15 13 -3 — 3 2 — 4 б б 5 5 4 4 1 1 3 2 — 4 — 2 — б — 4 12 15 — 3 — 3 2 2 — б — б — 5 5 4 4 1 1 4 4 — 4 — 4 — 5 — 5 13 -3 г — 6 5 — 1 1 4 — 5 5 13 15 — 3 -3 2 2 -б -б — 5 — 5 — 1 4 1 1 5 5 — 4 — 4 — 1 — 4 Х[1] Х [2] Х [3] Х(4] Х [5] Х(б] Читать столбцы слева направо. В момент и цикл (163) уже был обращен.
Программа 1 (Обращение на месте). 111 = т; г12 = — 1; г13 = 1' и и = й (этот символ определяется, когда программа транслируется как часть большей программы). И 1НИНН1 1111 И 1 ~~1. И бг ЕИТЗ -1 1 у »- — 1. Алгоритм 1 (Обратнал перестановка на месте). Заменить Х(1]Х(2]... Х(п), которая является перестановкой чисел (1,2,...,п), обратной перестановкой.
Этот алгоритм был предложен Вин-Чао Хуаном (В1п8-СЬао Нпапб) (1пб Ргос. 1,еыегэ 12 (1981), 237-238]. 11.(Инициализация.] Присвоить т » — и, у »- — 1. 12. [Следующий элемент.) Присвоить 1»- Х[т]. Если 1 < О, перейти к шагу 15 (этот элемент уже был обработан). 13. [Обратить один элемент.] (В этот момент 1' < О и 1 = Х[т]. Если т не является наибольшим элементом своего цикла, то первоначальная перестановка давала Х[-1] = т.) Присвоить Х(т) +- 1, 1»- -т, тп +- 11 4 +- Х[т). 14. (Конец цикла?] Если 1 ) О, перейти к шагу 13 (этот цикл не закончен); иначе— присвоить 1 +- 11 (В последнем случае первоначальная перестановка давала Х[ — 1) = т, где т — наибольший элемент в его цикле.) 15.
(Сохранить окончательное значение.] Присвоить Х[т)» — — Е (Первоначально Х[ — 1) было равно т.) 16. [Цикл по т.] Уменьшить т на 1. Если т > О, перейти к 12; в противном случае работа алгоритма заканчивается. 1 Пример данного алгоритма приведен в табл. 3. Этот метод основан на обращении последовательных циклов перестановки; для пометки обращенных элементов их делают отрицательными, а впоследствии восстанавливают первоначальный знак.
Алгоритм 1 частично напоминает алгоритм А и очень сильно напоминает алгоритм нахождения циклов, реализованный в программе В (строки 54-68). Таким образом, это типичный представитель алгоритмов, имеющих отношение к перестановкам. Во время подготовки его реализации для 811 было обнаружено, что удобнее всего сохранять в регистре величину — 1, а не саму 1.
Время выполнения этой программы легко подсчитать способом, о котором говорилось выше. Каждому элементу Х[т] сначала присваивается отрицательное значение на шаге 13, а затем — положительное на шаге 15. Общее время выполнения составляет [14Ф+ С+ 2)и, где гэ' — размерность массива, а С вЂ” общее число циклов. Ниже будет проанализировано поведение С в случайной перестановке. Почти всегда существует несколько алгоритмов решения любой поставленной задачи, поэтому можно ожидать, что есть еще один способ обращения перестановки. Следующий остроумный алгоритм был предложен Дж.
Бутройдом [3. ВоогЬгоуг)). Алгоритм 3 [Обращение на месте). Этот алгоритм дает такой же результат, как н алгоритм 1, но на основании другого метода. 31, [Сделать все величины отрицательными.] Присвоить Х [1г] г — — Х [1] для 1 < Й < и. Присвоить также т э- и. 32. (Инициализация 1.] Присвоить 1 э- т. 33. [Нахождение отрицательного элемента.] Присвоить г г- Х[г].
Если г > О, присвоить г э- г и повторить этот шаг. 34. [Обращение.] Присвоить Л [г] +- Х[ — 1], Х[ — г] +- т. 35. [Цикл по т.] Уменьшить т на 1; если т > О, вернуться к шагу д2. В противном случае работа алгоритма заканчивается. 1 Пример выполнения алгоритма Бутройда приведен в табл. 4. В сущности, в основе метода опять лежит циклическая структура, но в данном случае то, что алгоритм действительно решает поставленную задачу, гораздо менее очевидно. Мы предоставляем читателю проверить это самостоятельно [см. упр, 13). Программа 3 [Аналог программы 1).
гП = т; г12 = э; г13 ив з — Е 01 1ИЧЕНТ ЕИИ1 И 1 00 зт1 1+и+1,110:О) л Ов 1ИС1 1 1У 04 1!И э-2 1У 05 ЕИТ1 И 1 ОВ 2Н ЕИИЗ 0,1 1У 07 ЕМИ2 0,3 А ов 103И Х,2 А ВЕ С елэть все величины от и агельными. Установить отрицательный знак. Ещеу т+- и. ~и„, „ В э — 1. ВВ. Нахож ение от и ательэого элемента. 0В 2Н 04 ов зн ов 07 ов Оо 4Н 10 11 5Н гв 6Н 10 Е02И Х,1 Вгр 5Р ' зтз Х,1 ЕИИЗ 0,1 ЕИИ1 0,2 Игн Х,1 32И ЗВ ЕИИ2 0,3 ЗТ2 Х,1 ОЕС1 1 .11Р 2В 7э' 12. Сле ю ия элемент. 1+- Х[т).
Х Переход к шагу 15, если 1 < О. 1У 13. Об эгить элемент. Х[т) +- 1'. 1У В +- — т. М т+-1. гу 1 Ф- Х[т). ЭКИ ° ЕП... ° Э, . а С В противном случае присвоиты +- гз 1У 15. Сох злить окончательное значение. Х[т) +- -1, ж кл Ф Переход к шагу 12, если т > О. 1 Таблица 4 ОБРАЩЕНИЕ ПЕРЕСТАНОВКИ 621543 С ПОМОЩЬЮ АЛГОРИТМА 1 После шага Л2 ЛЗ Л5 ЛЗ -б — 6 — б — б -2 — 2 — 2 — 2 — 1 — 1 б б — 5 — 5 — 5 -5 -4 — 4 — 4 — 4 — 3 — 3 — 1 — 1 б б 5 5 -3 — 3 — 4 б б б 5 ЛЗУ а-2 БРА Х,З ЯТА Х,2 ЯТ1 Х,З РЕС1 1 Л1Р 2В А 1>О? Ж 1У Х[1] +- Х[ — 1]. 1У Х[-1]+- т. О дарр Х Переход к шагу Л2, если т > О 5 Чтобы выяснить, насколько быстро работает данная программа, нужно знать величину А; она настолько интересна и поучительна, что мы оставили ее лля упражнения (см, упр.
14). Хотя алгоритм Л невероятно изящен, анализ показывает, что алгоритм 1 намного его превосходит. На самом деле оказывается, что среднее время выполнения алгоритма Л, в сущности, пропорционально п 1и и, а среднее время выполнения алгоритма 1 пропорционально и. Возможно, кто-нибудь когда-нибудь найдет применение алгоритму Л (или некоторой его модификации); это слишком изящный алгоритм, чтобы его можно было совсем забыть.
Замечательное соответствие. Как уже отмечалось, запись перестановки в циклическом виде не единственна; состоящую из шести элементов перестановку (1 6 3)(4 5) можно записать как (5 4)(3 1 6) и т. д. Поэтому полезно рассмотреть каноническую форму циклического представления, которая является единственной. Для получения канонической формы выполните следующие действия. а) Выпишите явно все единичные циклы. Ь) Внутри каждого цикла поместите на первое место наименьшее число. с) Расположите циклы в порядке убывания их первых элементов. Например, для перестановки (3 1 6)(5 4) получим (а): (3 1 6) (5 4) (2); (Ь): (1 6 3) (4 5)(2); (с): (4 5) (2) (1 6 3). (20) Важным свойством этой канонической формы является то, что скобки можно удалить, а затем восстановить единственным образом. Следовательно, расставить скобки в "4 5 2 1 6 3" для получения канонической циклической формы можно только единственным способом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
