AOP_Tom3 (1021738), страница 179
Текст из файла (страница 179)
5. (Х вЂ” 1) + (Х вЂ” 3) + = (Л'~/4). 6. (а) Если на шаге БЗ окажется, что г ф 1', то после его выполнения число инверсий уменьшится на 2гп — 1, где т на гдиннну больше числа ключей, лежащих в интервале пожду К, и К, среди Кг4г... К, ь Ясно, что пг не меньше, чем вклад в значение параметра В на предыдущем шаге Б2. Примените теперь следствие из упр. 4, связывающее циклы с условием г' = у (Ъ) Любую перестановку можно получить из Лг... 2 1 путем последовательных взанмообменов соседних элементов, которые нарушают исходное упорядочение. (Примените в обратной последовательности те обмены, под действием которых перестановка сортируется в порядке убывания ) Каждая такая операция уменьшает 1 на единицу н излгеняет С на *1. Следовательно, ни для одной перестановки значение 1 — С не превосходит соответствующего значения для Аг.. 2 1.
[Иэ упр. 5 вытекает, что неравенство В < [Аг'/4] — наилучшее из возможных ] 7. В работе А С. г'ао, Оп ясса!Яйс зе!ессюп загс (Сопгрцсаг Ес!енсе Тес)гп!са! Каросс 185, Рппсесоп 1)п!тегясгу, 1988), показано, что дисперсия равна адг'~ + 0(Ксгзл !о8 Н), гдг а = А" г/я)п г — 0.9129. В ней также высказано предположение, что в действительности составляющая ошибки значителъно менъше. 8. Можно начинать очередную итерацию шага 82 с позиции Кп поскольку мы запомнили псах(Кг,...,К, г). Один иэ способов учета всей этой дополнительной информации— использование таблицы связи Ьг .. 5;ч, таков, что Кс„равно предыдущему вылеченному элементу всякий раз, когда Кл также выделено; Хг — — О. [Тот же результат можно получить, используя меньший объем дополнительной памяти, "заплатив" за зто лишней операцией сравнения.] В приведенной ниже И1Х-программе применяется модификация адреса в хозе выполнения, которая ускоряет реализацию внутреннего цикла.
Исходное состояние регистров таково: гП г— н 1, г12 = !с — 1, г13 = г, гА = К,. 01 ЯТАКТ ЕИТ1 М 1 1+- Ю. 02 ЯТ2 АТМЕ+1 ! 02 зир 9Р 1 О.! 1Н ЯТ1 6Р10 г 2) Аг — Р Модификация адреса во внутреннем цикле. 05 ЕИТ4 1МРС)Т„1 Н вЂ” Р Об ЯТ4 7Р ОО г 2) Ас — Р 07 ЕМТ4 11МК,1 Аг — Р Об ЯТ4 ВР(0:2) 1лг — Р 09 7Н СИРА 1ИРОТ+1.2 А (Адрес модифицирован] 10 10Е с+4 А Переход, если К, > Кл. 11 ВН ЯТЗ 11ИК+1,2 Н + 1 — С Иначе — Ьл +- г. [Адрес модифицирован] 12 6Н ЕМТЗ з,2 Аг+ 1 — С г+- Сг. [Адрес модифицирован,' 10 Ы)А ХМРОТ, 3 )'гг + 1 — С 14 1ИС2 1 А )с г- )г+ 1. 15 12МР 78 А Переход, если сс < 1. 1б 4Н 101 1ИРОТ,1 АС 17 ЯТХ 1МРОТ,З Н В, +- В,.
1б ЯТА ТИРОТ,1 Н Н, г- предыдущее значение Н,. 10 ОЕС1 1 1'г' 1 +- 1 — 1. 20 ЕМТ2 0,3 Ж И2+- г. 21 КОЗ 11ИК,З глг . г г- Ьч. 22 13МХ ВР Ж Если г > О, А начнет с г. 22 9Н ЕИТЗ 1 С Иначе — г г — 1. 24 ЕИТ2 2 С )г начнет с 2. Яб ЯИ ОЕС2 0„1 )'гг+ 1 Яб 1.ОА 1МРОТ,З )Сг + 1 гА г- К,. Я7 12МР 18 07+ 1 Переход, если Сс < 1.
Яб 11Р 48 Р+1 Переход, если) > О. $ 9. Аг — 1+ 2 л>с> (()с — 1)/2 — 1/й) = -'(г) + Ж вЂ” Нл. [Средние значения параметров С и Р равны Нлг + 1 и Нн — -' соответственно. Следовательно, среднее время выполнения г программы равно (1,25Ю + 31.751Сг — 15Нлг + 14.5) и.] Программа Н работает значительно лучше. 10. Г' 'ч, 087 061 -оо -оо -оо -оо -оо -оо /~ /~ /~ /~ /~ /~ /~ /~ -оо 087 -со 061 -оо -оо — со — оо — оо — оо — оо -оо -оо -оо -~ -оо г /~ /~ П /~ /~ /~ /~ П -оо -оо — оо -оо -со -со -оо -оо -оо — со 154 — оо 612 -оо — оо — оо 12. 2" — 1, один рэз для каждого -оо в узле ветвления 13. Если Л > К„4.п то после шага Н4 можно переходить к шагу Н5 при 1' = г. (На шаге Н5 ничего не делается, если не выполнено условие Л, < К„ьб в этом случае на шаге Нб обязательно произойдет переход к шагу Нб.) Чтобы на протяжении всего алгоритма обеспечить выполнение условия К > К, гп можно начать с Кя44 < ппп(Кп ..,,Кл).
Вместо присвоения К < — К~ на шаге Н2 установим К„44 4 — Ель~ и Кл.ьг +- ИЫ установим также Кз 4- Кл4~ после того, как выполнится условие г = 1. (Этот прием не ускоряет алгоритм и не укорачивает программу Н.) 14. Чтобы получить простую очередь (или стек), вставляя элемент, приписывайте ему ключ, меньший (соответственно больший) всех ранее присвоенных ключей. 15. Так как преследовалась пель повышения эффективности, следующее решение несколько замысловато: в нем пропускаются все числа, кратные 3 [САС54 10 (1967), 5?О). Р1. Установить р(1) +- 2, р(2) 4 — 3, ?г 4- 2, и 4- 5, г( +- 2, г +- 1, 1 4 — 25 и поместить в приоритетную очередь элемент (25, 10,30). (В этом алгоритме р(1) —. 1-е простое число, )с — количество найденных до сих пор простых чисел, и — кандидат в простые числа, И - — расстояние до следующего кандидата, г — число элементов в очереди, 1 = р(г+ 2) з — — следующее значение и, для которого надо увеличить г.
Элементы очереди имеют вид (и, е, бр), где р — наименьший простой делитель и, о = 2р илн 4р и и + о не делится на 3.) Р2. Пусть (д, д', 0") — элемент очереди с наименьшей первой компонентой. Замените его в очереди на (д+ ц', дв — 0',0"). (Это означает следующий множитель 0"/б, который должен быть исключен.) Если и > д, повторять этот шаг до тех пор, пока ие станет п к 0. Р3. Если и > Лг, прекратить выполнение алгоритма. В противном случае, если и < 0, установить ?с 4 — )с + 1, р()с) +- и, и 4- и+ б, ы +- б — ы и повторить этот шаг.
Р4. (Теперь и = д — непростое число.) Если и = 1, установить г !- г+ 1, и е — р(с+2), ! +- в~ н вставить в очередь либо (1,2и,бк], либо (1,4и, би), если и шод 3 = 2 нлн и шо63 = 1 соответственно. Р5. Устшювить п !- и+ И, 6 е- 6 — 6 и вернуться к шагу Р2 1 Начало вычислений выглядит следующим образом. Содержимое очереди (25, 10, 30) (35, 20, 30)(49, 28, 42) (49, 28, 42)(55, 10, 30) (55, 10, ЗО)(77, 14, 42)(121, 22, 66) Найденные простые числа 5, 7, 11, 13, 17, 19, 23 29, 31 37, 41, 43, 47 53 Если очередь реализована в виде пирамиды, то можно найти все простые числа < 07 за О(!У!оба) шагов: размер пирамиды не превышает количества простых чисел < эГХ. Решето Эратосфена (реализация приведена в упр.
4.5.4 — 8) — метод с нременем выполнения порядка О(М (аб !об Ю), требующий значительно больше памяти с произвольнгям доступом. Более эффективные методы реализации будут рассмотрены в разделе 7.1 16. 11. Установить К е- вставляемый ключ, 1 +- и + 1. 12. Установить ! э- (1/2!. 13. Если ! = 0 или К, > К, то установить К э- К и прекратить выполнение алгоритма. 14. Установить К, !- Кп 2 е- ! и возвратитыя к шагу 12. 1 (В рабате Т.
Рогсег, 1. 8!шоп, !ЕЕЕ Тгэлэ. ВЕ-1 (1975), 292-298, показано, что если задана случайная пирамида иэ равномерно распределенных чисел и Л„.ь~ — среднее число случаев выполнения шага 4, то получится А„= ()бп) + (1 — п ')А„при и > 1, где и = (1Ь| ~Ь| з...бе)э вл~ кт за собой и' = (1Ь~ э.
Ье)ь Если ! = (!8п1, эта величина всегда > Азы~, = (2ьы — 2)/(2ьы — 1) и всегда < Ар < и, где а — константа в (19).) 17. Алгоритм Н преобразует массив 1 2 3 в пирамиду 3 2 1, а алгоритм из упр. 16 преобразует его в пирамиду 3 1 2. (Замечание. Время выполнения этого последнего алгоритма построения пирамиды в наихудшем случае составляет порядка !У !об !У, но эксперименты показали, что для случайного исходного массива шаг 2 во время построения пирамиды выполняется всего около 2.28% раз В работе В. Наукагб, С.
МсП!агшк(, э' А!8опНппв 12 (1991), 126. 153, строго доказано, что значения постоянных коэффициентов пропорциональности лежат между 2 2778 и 2.2994.) 18. Удалите шаг Нб и замените операции на шаге Н8 следующими операциями. Н8'. (Продвинуться обратно вверх.) Установить 1 < — 1, ! +- (у/2), Н9'.
(Подходит ли К7] Если К < К, или 1 = 1, установить 27з е- й и возвратиться к гиагу Н2. В противном случае установить Я, е- 77, и возвратиться к шагу Н8'. 5 Это, по существу, тот же метод, что и в упр. !6, но с другой начальной точкой в пирамиде. Массив изменяется так же, как в алгоритме Н. Эмпирические проверки этого метода показывают, что число присвоений й, е- Н„приходяигихся на одну операцию протаскивания в фазе выбора, равно (0,1,2) с вероятностями (.837, .135, .016) соответственно Этот метод несколько удлиняет программу Н> но повышает асимптотическую скорость до 1ЗХ !8Х + 0(Х). 2Кглательна иметь в системе команд И11 команду деления пополам содержимого индексного регистра В работе С. Л.
Н. МсП!агш!6, В. Л. Вееб, 1. А!8ог!г!ипэ 10 (!989), 352 — 365, доказано, что прн такой модификации сохраняется в среднем (ЗД вЂ” 8)!У вЂ” 0.232!У сравнений на этапе формирования пирамиды, где 6 определено в ответе к упр. 27. Более углубленный анализ модификаций Флойда приведен в работе 1. Ч~ебепег, ТЬеогейса1 Сошр, Ясй 118 (1993), 81.98. В работе Л. Ъц, Н.
ИЬц, Х Сошр. Ясй и Тесб. 9 (1994), 261 †2, высказано соображение, что может быть использован и метод двоичного поиска, так что каждая операция протаскивания на фазе выбора будет включать не более 181э'+ 1818 Ж сравнений и 18Х перемещений записей. 19. Действуйте так же, как в измененном алгоритме протаскивания (упр.
18), установив значения К = Кя, 1 = 1 и г = Х вЂ” 1 с заданного значения У на шаге НЗ. 20. При О < й < и количество положительных целых чисел < Ю, двоичное представление которых имеет вид (Ь„... Ьь ам .. аэ)э при некотором д > О, равно, очевидно, (Ьь ~... Ье) э+ 1+ 3-„„„2 = (15,,...Ь.),. 21.
Пусть 1 = (с ... се)е принадлежит интервалу (Х/2~"') = (Ь„... Ььэ,)з < 1 < (Ь„... Ьь)г = (Х/2~). Тогда э, равно количеству положительных целых чисел < 7э', двоичное представление которых — суть (с,... совы .. аэ)е при определенном 9 .~ О, а именно 2 „< „2э = 2 г — 1.
Следовательно, число неособых деревьев размером 2ьы — 1 равно д ьы (Для вывода последнего тождества воспшо*зуйтесь репликативным законом из упр. 1.2.4-38 при л = 2 и х = Х/2~~ '.) 22. До того как станет 1 = 1. пять возможных вариантов таковы: 5 3412, 35412, 43512, 15432 н 25413.
Каждый из этих вариантов а~аэазаэаз приводит к трем перестановкам (а~аеазаэаы а~аэазаэае., а~азаэоеаз), возможным до того, как получим1 = 2. 23. (а) После В итераций имеем 2 > 2" 1; следовательно, 2в1 < г. (Ь) Имеем (1абз (Х/1)) = ((Ж/2) — (Х/4)) + 2((Ж/4) — (74(8)) + 3((Х/8) — (Х/16)) + [=1 = '11э'/21+ (Х/4) + (Ж/81 + = Х вЂ” ~(Х), где и(1э') — число единиц в двоичном представлении числа Х, Из упр. 1.2.4 — 42 получаем также 2 ~,'(18г) = Ж(181т) — 20эн~ '+2. Из теоремы Н известно, что эта верхняя оценка для величины В .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
