AOP_Tom3 (1021738), страница 171
Текст из файла (страница 171)
дт и 179 904 из них находятся на расстоянии < 5 от порядка в молекуле ДНК табака. [Эффективный алгоритм поиска наилучшего способа сортировки любой перестановки со знаком посредством реверсирования был изложен в работе Б. Напиелба!!1, Р. Регзпег, ХАС51 46 (1999), 1 — 27, а усовершенствован — в работе Кар!ап, БЛащ»г, Тзгзал, БОРА 8 (1997), 344-35Ц 43. Обозначим компоновкУ наподобие дт д,д,д„дзд,дв посРедством пеРестановки со знаком д д 7124536. Если существует отрицательный элемент, например Л, но отсутствует Л вЂ” 1, одна операция перебрасывания создаст двойной цикл ((Л вЂ” 1)дйь). Аналогично, если имеется Л, но отсутствует й + 1, одинственная операция перебрасывания сформирует (Лл (5+1) т.).
И если все операции таз»ого вида ут»аляют все отрицательные элементы, то единственное перебрасывание формирует два двойных цикла. Если отсутствуют отрицательные элементы, а перестановка не рассортирована, некоторые из перебрасываний бу;чут сохранять количество циклов.
Следовательно, за < и перебрасываний можно выполнить сортировку, если данная перестановка имеет отрицательный элемент; в противном случае необходимое количество перебрасываний составит < и + 1. Если и четное, перестановка и (и — 1) ... 1 требует и+ 1 перебрасываний, поскольку в ней будет один цикл после первого перебрасывания. Если п > 3 почетно, то, рассуждая аналогично, приходим к выводу, что для перестановки 2 1 3 п (и — 1) ...
4 потребуется и+ 1 операция. 44. Пусть с» — число циклов длиной 2Й н мультиграфе из ответа к предыдущему упражнению. Верхняя грш»ица для среднего значения с» может быть найдена следующим образом. Обп»ее число потенциальных 28-циклов равно 2 (и+ 1) — /(2Й), поскольку мы можем » » ныбрать (я+ 1)» способами последонательность Л различных ребер из (Од — 1»,, дд— (и+ 1)с) и ориентировать их 2" способами. Таким образом, каждый цикл будет подсчитан 2Й раз, включая и невозможные случаи наподобие (1д 2», 2д Зь), (1л 2» Зь 2д Зд 4»,) и (1д 2», бл 7» 4» Зд 2л Зь бь 5д) Если Л < и, каждый возможный 28-цикл появляется точно в 2" »(и — Л)! перестановках со знаком. Например, рассмотрим случай, когда Л = 5, РАЗДЕЛ 5.2 1.
Да; «и 3 могут изменяться н диапазоне 1 < 1 < 1 < /««в произвольном порядке. Это позволяет выполнять подсчет параллельно с вводом данных. 2. Сортировка будет устойчива в том смысле, как определено н начале этой главы, поскольку алгоритм, по существу, выполняет упорядочение в лексикаграфическом порядкеразличающнхсл пар ключей (Ки 1), (Км 2),,[Кя, Ф). (Если представить себе, что к каждому ключу справа добавлен его адрес в файле, то равных ключей не будет, а значит, сортировка будет устойчива.) 3. Программа все-таки будет выполнять сортировку, но это будет неустойчивая сортировка. Егли К, = К,и ) < г, то, в конце концов, Ну окажется восле Л,.
Кроме того, внесенные изменения замедлят работу программы С. 4. ЕИТ1 И 1 БТА ООТРОТ+1,2 70 102 СПОЕТ,1 Х ПЕС1 1 Х 1.ПА 1ИРОТ,1 Х 11Р е-4 Х ) 5. Время выполнения уменьшится на А+ 1 — )У вЂ” В машинных циклов, и это почти всегда можно рассматривать как существенное улучшение. 6. в=О,п=9.. После [)1 После П2 После П4 Во нремя 05 О О О 2 2 1 4 5 2 3 5 О 0 0 3 2 1 12 14 15 9 12 15 — — 51. БТ БО ББ О 1 16 16 /=В БА 6Т 61 70 7И вЂ”вЂ” БА 6Т 61 70 78 85 9 СОПИТ = СОПИТ = СОПИТ = СОПИТ = ООТРОТ = ОПТРПТ = О О О О 1 3 5 6 9 5 5 В 10 — 4А 10 28 4А После [)5 ОС 00 18 7. Да; обратите внимание на то, что СОПИТ[К,) уменьшено на шаге Вб, а затеи уменьшается 1.
В. Сортировка будет выполняться, на не будет устойчивой [см. упр 7). 9. Пусть Ау = в — а; будем считать, что !в) н !«) умещаются в два байта. 1.0С(Нэ) ы 1МРОТ и); БОС(СОПИТ[11) — ш СООМТ+/б БОС(8,) = ОСТРОТ+/; гП э— э И г12 = /; г13 ш 1 — е или г13 = 7«;. М ЕОО У-О КЕТ ЕЦО О:2 (Сопутствующая информация в байтах 3:5) и = 9 и имеется цикл (Ол 1« 9« Вя 7л Вь 1я 2« 5« 4л). Этот цикл появляется в мультиграфе тогда и только тогда, когда перестановка со знаком начинается с 4 и содержит надцепочки 9187 и 25 или их реверсы.
Все решения можно получить, если найти все перестановки со знаком множества 11,2,3,6) и заменить 1 значением 9187, 2 — значением 25. Значит, Ес«< 1/(2А) 2«(и + 1)«2" «[и — й)!/2"и! = 1(1/)с + 1/(и + 1 — А)). Из этого следует, что Ес = 2 „", Ес«+ Ес4Ы < Н„+ 1. Поскольку и+ 1 — с — нижняя граница числа перебрасываний, нам понадобится > и + 1 — Ес > и — Н„из ннх. )В этом доказательстве использована идея В.
Вафна (Ч. Ва[па) и П. Певзнера (Р. Реехпег), ЯСОА4Р 25 (1996). 272 .289, которые изучали более сложную проблему сортировки перестановки без знака посредством реверснрования. В этой задаче рассматривались перестановки, которые могут быть записаны в аиде произведения неразрезанных циклов (1 2 3) [3 4 5)(5 6 7) ., оканчивающихся либо на [л — 1 и), либо на (и-2 и-1 и) в зависимости от того, каким является и: четным или нечетным.
Оказалось, что такие перестановки труднее всего сортировать.) н < г < и. вг. л в.в в. Р1. [Цикл по г!) Выполнить шаг Р2 для 1 < г < Аг; затем завершить выполнение процедуры. Р2. [Р(г) = г?) Выполнить шаги с РЗ по Р5, если р(г) ф г.
РЗ. [Начало цикла.) Присвоить С с — Кь ? +- Е Р4. [05Реботать ггг.) ПРисвоить /с +- Р((), )?, +-??ю Р(Я +- ?, 2 +-?с, Если Р(!) М повторить этот шаг. Р5. [конец цикла.] присвоить )т; г — г, р()) г — 1. Этот алгоритм изменяет р(г), поскольку в приложениях, использующих сортировку, можно считать, что р(г) хранится в оперативной памяти. С другой стороны, существуют приложения, такие как траиспонирование матриц, в которых р(г) является функцией г, т. е. ега для экономии памяти необходимо вычислять, а не считывать из таблицы В атом сггучае можно использовать следующий метод, выполняя шаги ат В1 да ВЗ для 1 < г < Ж. В1.
Присвоить lс г — р(г) В2. Если А > г, присвоить?с г- р(А) и повторить этот шаг. ВЗ. Если А < г, ничего не выполнять, но если lс = г (это означает, чта г — наименыпее в своем цикле), то переставить операции цикла, связанные с г следующим образом. 1Н ЕММЗ М 1 1)!. Очистка СОВЕТ. БТ2 СООМТ+г,З М+ ! СОСЕТ!е — ?с] г- О. 1МСЗ 1 М + 1 АЗЕР в-2 М+1 а<с<и 2Н ЕМТ2 М вгл ЗН ООЗ 1МРОТ,2(КЕТ) Аг О.3. Увеличить СООМТ К ЕОА СОНЕТ,З Х 1МСА 1 Аг БТА СОСЕТ,З Х ОЕС2 1 Аг 12Р ЗВ Аг А'>) >О.
ЕММЗ М-1 1 1)4. Накопление. ООА СОНЕТ+О 1 гА г — СОСЕТ(г' — 1]. 4Н АОО СОНЕТ+7,3 М СОСЕТ П вЂ” 1] + СООМТ(г] БТА СОНЕТ+7,3 М ч СОВЕТ[с]. 1МСЗ 1 М )ЗМР 4В М 5Н ЕМТ2 М 1 ОН 103 1МРОТ,2(КЕТ) Аг 1.01 СООМТ,З Аг г г- СОНЕТ(К,]. ЕОА 1 КРОТ, 2 Аг гА+- Н,. БТА ООТРОТ,1 Аг 5, г — гА. ОЕС1 1 Аг БТ1 СОВЕТ,З Аг СООМТ ГКг ] +- г — 1.
РЕС2 1 Лг 32Р 6В г'г' Аг >1'> О $ Время выполнения — (10М+ 22Аг+ 10)н, 10. Чтобы не использовать дополнительно Аг бнт для "маркера' [см раздел 1.3.3 и СуЬеглепсэ 1 (19б5), 9о) и при этом все-таки оставить время выполнения пропорциональным Аг, можно использовать следующий алгоритм, основшгный на циклической структуре перестановки. Присвоить (» — ЛП затем. пока р(й) Ф 5, повторять присвоения Л»» — Лр(к) и й+- р(й)) и, наконеп, присвоить Л» +- С 3 Этот алгоритм аналогичен процедуре, описанной в работе 3. Воо»)»гоу»(, Сол»р.
Х 10 (1967), 310,но требует меньшего количества операций перемещения данных; несколько усовершенствованный алгоритм предложил И. Д. Г. Мак-Леод (1. В. О. Мас1,ео»1) [Аиэ»гайал Со»пр. и'. 2 (1970), 1б — 19). Анализ, выполненный для случайной перестановки в упр. 1.3.3-14, показывает, что шаг В2 выполняется в среднем (Л) + 1)Нл — Л раз. (См. также ссылки на литературу в ответе к упр. 1.3.3-12,) Аналогичный алгоритм можно разработать и для того, чтобы заменить (Лр(),..., Лр(к)) на (Л),..., Лн), например, если перекомпоновка в упр. 4 должна быть выполнена при условии ОСТРОТ = 1ИРОТ. 11. Пусть гП = 5, г12 кз )'; г13 = й; КХ Вз с 1Н ЕИТ1 И Р .и ~~~ 2Н СИР1 Р,1 ЗЕ 8Р Ж Перейти, если р(5) = 5.
5 — В РВ. Н,. НН Еитг 0,1 А — В ) »- 5. 4Н 103 Р,2 ЛР— А Р4. За икси овагь Л . й» вЂ” р()'). 104 1НРОт,з Л) — А 814 1ИРОТ,2 5"5' — А Л +- ЛВ. ЗТ2 Р,2 79 — А р(у)» — 11 ЕИТ2 0,3 Л) — А (»- й. СИР1 Р,2 )В' — А ЗИЕ 48 5ЛР— А Повторить, если р(7) ~ 5. »г 5 55, 5 — В Р~5. К Н, ЗТ2 Р,2 А — В Р(7) 4 20 8Н ОЕС1 1 ЛР 11Р 28 Л'>5>1. 1 Время выполнения равно (17ЛР— ЗА — 7В+ 1) и, где А — число циклов в перестановке р(1) ., Р(ЛР) и  — число неподвижных точек перестановки (единичных циклон) Патучим В=) 5 5, Н, НВ ВН -В ) В=) ' 5, 5, НР» 5) для ЛР > 2 в соответствии с 1.3.3-(21) и 1.3.3-(28).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
