Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 78
Текст из файла (страница 78)
Исходное состояние регистров таково: г11 ш 1, г12 ш (г — 1, г13 ш 1, гА еа К,, 01 ЗТКНТ ЕИТ1 И 1 1<-А( 08 ЗТ2 СТИХ+1 1 08 ХНР 9Р 1 04 1Н ЗТ1 ВР(0: 21 Н вЂ” Х1 Модификация адреса во внутреннем цикле. 06 ЕИТ4 1ИРОТ, 1 Ф вЂ” Ху 06 ЗТ4 7Р(0: 21 Аг — Ху 07 ЕИТ4 1 ХИК, 1 Ж вЂ” Ху 08 ЗТ4 ЗР(0:2) Аг — О ОУ 7Н СИРА 1ИРОТ+1.2 А [Адрес модифицирован[ 10 10Е в+4 А Переход, если К; > Кв, 11 ВН ЗТЗ 11НК+1,2 Аг+ 1 — С Иначе — Хв +- Е [Адрес модифицировал[ 18 ЗН ЕИТЗ 1.2 К+1 — С 1 <- й. [Адрес модифицирован[ 18 104 1ИРОТ,З Аг + 1 — С 14 1ИС2 1 А В в- В+ 1. 16 12ИР 78 А Переход, если В < 1.
16 4Н ХВХ ТИРОТ, 1 АГ 17 ЗТХ ТИРОТ,З Н Н Ф-Н,. 18 зта 1иРОт, 1 Аг Яв в- предыдущее зиачеине Но 1У ОЕС1 1 Ф 1 ~-1 — 1. 80 ЕИТ2 0,3 Ж г12 в- Е 21 СОЗ ХХИК,З Н 1+- Ео ЗЯ ЛЗНХ БР Н Если 1 > О, й начиет с К 88 9Н ЕИТЗ 1 С Иначе — 1 в- 1. ЯХ ЕИТ2 2 С В иачпег с 2. 86 ЬИ ОЕС2 0,1 Аг+ 1 86 104 1ИРОТ,З АГ+ 1 гА в- Кь 87 12ИР 1В Аг+ 1 Переход, если й < 1, 88 11Р 4В О 41 Переход, если,1 > О, $ 9.
10 — 1+ Х в>в> (((г — Ц12 — 1ХВ) = -'(в) + Ж вЂ” Нл. [Средние значения параметров С и .О равны Нл + 1 и Нл — 1 соответственно, Следовательно, среднее время выполнения 3 э программы равно (1.25Ф + 31.75А( — 13Нл + 14.5) и.[ Программа Н работает значительно лучше. 10. 667 061 -ос -со -со -оо -со -оо /~ /~ /~ /~ /~ /~ /~ /~ -со 067 -оо 061 -оо -оо -оо -оо -оо -со — со -оо -оо -оо -оо -оа -ос -со -со — ос -со -сс — со -оо -со — оо 154 — со 612 -оо -со -со 12. 2" — 1, один раз для каждого -со в узле ветвления.
13. Если К > К,~. м то после шаха Н4 можно перехсщить к шагу Нб при у' = г.. (Иа шаге Н5 ничего не делается, если не выполнено условие К, < К,ьм в этом случае на шаге Нб обязательно произойдет переход к шагу Нб.) Чтобы на протяжении всего алгоритма обеспечить выполнение условия К > К,ьп можно начать с Кл~~ < ппп(Кь...,Кл) Вместо присвоения й„г- Вг на шаге Н2 установим й,е~ <- Виег н Кл+г э- Л-„установим также Вэ +- Ки~~ после того, как выполнится условие г = 1. (Этот прием не ускоряет алгоритм и не укорачивает программу Н,) 14.
Чтобы получить простую очередь (или стек), вставляя элемент, приписмвайте ему ключ, меш ший (соответственно больший) всех ранее присвоенньгх ключей. 15. Так как преследовалась цель повышения эффективности, саедующее решение несколько замысловато: в нем пропускаются все числа, кратные 3 [САСМ 10 (1967), 570). Р1. Установить р[1) ~- 2, р[2[ +- 3, я г- 2, и +- 5, 4+- 2, г ь- 1, $ е- 25 и поместить в приоритетную очередь элемент (25, 10, 30), (В этом алгоритме р[1] — - бе простое число, 7г — количество найденных до сих пор простых чисел, и — кандидат в простые числа, И вЂ” расстояние до следующего кандидата, г — число элементов в очереди, 1 = р[г+ 2)т — следующее значение и, дла которого надо увеличить г, Элементы очереди имеют вид (и, е, бр), где р — наименьший простой делатель и, с = 2р илн 4р и и+ с не делнтси на 3.) Р2.
Пусть (д, д', д") — элемент очереди с наименьшей первой компонентой, Замените его в очереди на (д + д, д ' — д, д ~). (Это означает следующий множитель д"/б, который должен быть исключен.) Если и > д, повторять этот шаг до тех пор„ пока не станет и < д. РЗ. Если и > Л, прекратить выполнение алгоритма. В противном случае, есля и < д, установить (г г- )с+ 1, р[Ц г- и, и т- и+ г(, И ~.:— б — 4 и повторить этот шаг. Р4. (Теперь и = 9 — непростое число.) Если п = 1, установить г+- г+1, в 4- р(г+2), 1 +- из и вставить в очередь либо (1, 2в, бв), либо (1, 4в, бв), если в щаб 3 = 2 или в шоб 3 = 1 соответственно.
Рб. Установить н «- и+ «1, г(+- б — «1 и вернуться к шагу Р2. 3 Начало вычислений выглядит следующим образом. Содержимое очереди Найденные простые числа (25, 10, 30) 5, 7, 11, 13, 17, 19, 23 (35, 20, ЗО)(49, 28, 42) 29, 31 (49, 28, 42)(55, 10, 30) 37, 41, 43, 47 (оо, 10, 30)(77, 14, 42)(121, 22, 66) 53 Если очередь реализована в виде пирамиды, то можно найти все простые числа < )9 за О(!«(1об !«г) шагов; размер пирамиды не превышает количества простых чисел < «/К. Ре- шето Эратосфена (реализация приведена в упр.
4.5.4-8) — метод с временем выполнения порядка О(!«! !об !об )у), требующий значительно больше памяти с произвольным доступом. Более эффективные методы реализации будут рассмотрены в разделе 7.1. 16. 11. Установить К +- вставляемый ключ; У г — и + 1. 12. Установиты +- (у/2), 13.
Если ( = 0 или К; > К, то установить Ку +- К и прекратить выполнение алгоритма. 14. Установить К, 4- К;, У +- «'и воэвратитьси к шагу 12. $ (В работе Т. Роыег, 1. 8!шоп, 1ЕЕЕ Чгапэ ЯЕ-1 (1975), 292-298, показано, что если зада- на случайная пирамида иэ равномерно распределенных чисел и А„е« -- среднее число случаев выполнения шага 4, то получится А„= (!8н) + (1 — и' ')А„при и > 1, где и = (1Ь« — А-г ..Ьо)з влечет за собой н' = (15~ з...Ьа)з. Если ! = (!8и), эта величина всегда > Азы«, — — (2'+' — 1)/(2ьы — 1) и всегда < Ан < о, где и — константа и (19).,' 17. Алгоритм Н преобразует массив 1 2 3 в пирамиду 3 2 1, а алгоритм из упр.
16 преоб- разует его в ««ирамцлу 3 1 2. (Замечанве. Время выполнения этого последнего алгоритма построения пирамиды в наихудшем случае составляет порядка Ьу !об !«!, но эксперименты показали, что для случайного исходного массива шаг 2 во время построения пирамиды выполняется всего около 2.28!«! раз. В работе Н. Нау«гэгб, С. Мсй!агш!с1, з.
А!бог!гйшэ 12 (1991), 126-153, строго доказано, что значения постоянных коэффициентов пропорцио- нальности лежат между 2.2778 и 2.2994.! 18. Удалите шаг Нб и замените операции на шаге Н8 гледующими операциями. Н8'. (Продвинуться обратно вверх.) Установить У +- «, «+- (1/2) . Н9'. [Подходит ли К7) Если К < К; или г = 1, установить Лэ +- Л и возвратиться к шагу Н2. В противном случае установить Л +- Л, и возвратиться к шагу НЗ'.
$ Это, по существу, тот же метод, что и в упр. 16, на с другой начальной точкой в пирамиде. Массив изменяется так же, как в алгоритме Н. Эмпирические проверки этого метода показывают, чга число присвоений Л, +- Лч приходящихся на одну операцию протас- кивания в фазе выбора, равно (О, 1,2) с вероятностями (.837, .135, .016) соответственно. Этот метод несколько удлиняет программу Н, на повышает асимптотическую скорость ло 13)у!8 !у+ 0(К). Желательно иметь в системе команд ИХХ команду деления пополам содержимого ицлексного регистра.
В работе С. 1. Н. МсРАаппЫ, В. Л. Нееб, Х А18огй!ппэ 10 (1989), 352-365, доказано, что при такой модификации сохраняется в среднем (ǫΠ— 8))«! ш 0.232!«' сравнений на этапе формирования пирамиды, где Д определено в ответе к упр. 27. Более углубленный анализ модификаций Флойда приведен в работе 1. %ебепег, ТИеогеВса1 Сошр. Яс1 118 (1993), 81-98. В работе 3. %а, Н.
Ебп, Х Соп!р. Яс!1 и Тесй, 9 (1994), 261-266, высказано соображение, что может быть использован и метод двоичного поиска, так что каждая операция протаскивания иа фазе выбора будет включать не более 18 % + 18 187!' сравнений и 18 Х перемещений записей. 19. Действуйте так же, как в измененном алгоритме протаскивания (упр.
18), установив значения К = Кя, 1 = 1 и г = Х вЂ” 1 с заданного значения / на шаге НЗ. 20. При О < Ь < н количество положительных целых чисел < М, двоичное представление которых имеет вид (Ь„... Ььа!... ае)з при некотором д > О, равно, очевидно, (Ь| !... Ье)з+ 1+ ~ ес,<ь 2' = (15!-! Ьо)з 21. Пусть / = (с,...се)з принадлежит интервалу (Х/2~+'„! = (Ь„... Ьее!)т < / < (Ь Ьь)! = ()т/2~). Тогда з равно количеству положительных целых чисел < Х, двоичное представченне которых — суть (с,... сом!...
аз)т при определенном !7 > О, а именно ) „2е = 2ь+' — 1. Следовательно, число неособых !Юревьев размером 2" е' — 1 равно ()т/2") — (Х/2~~') — 1 = ((Ю вЂ” 2 )/2~+'). (Для вывода последнего тождества воспользуйтесь реплнкатнвным законом из упр, 1.2.4-38 при н = 2 н х = М/2~! !) 22.
До того как станет 1= 1, пять возможных вариантов таковы: 53412, 35412, 43512, 15432 и 25413. Каждый из этих вариантов а!азазаза! приводит к трем перестановкам (а! азазазам а! а!азизам а! о! аз а! аз), возможным до того, как получим 1 = 2. 23. (а) После В итераций имеем,1 > 2в1; следовательно, 2в! < г. (Ь) Имеем (1обз (!!!/1)) = ((М/2) — (!!!!/4)) + 2((М/4) — (Х/8)) + 3((Х/8) — (Ю/16)) + !=! ж ( 1Ч/2) + (й!/4 ! + (Х/8) + ° = М вЂ” и(г7), где и(Х) — число единиц в двоичном представлении числа Х Иэ упр. 1.2,4-42 получаем также 2" ~,'(18 г) = Х(18 Х) — 21!к я!э'+2, Из теоремы Н известно, что эта верхняя оценка для величины  — наилучшая из возможных на фазе построения пирамиды. Интересно, кроме того, отметить, что существует единственная пирамида нз ключей (1, 2,..., !!!), та кая, что в течение всей фазы выбора в алгоритме Н значение К тождественно равняется 1.
(При Х = 7, например, такой пирамидой будет 7 5 б 2 4 3 1; нетрудно осуществить переход от Х к Х+ 1.) На этой пирамиде и достигается максимальное значение В на фазе выбора пирамидальной сортировки (так же, как и макскмальное значение (Х/2) параметра В). Значит, верхняя граница значения параметра В, т. е. наилучшее значение из возможных для всей сартировкк, равно М вЂ” и(М) + Х(18 М) — 21!а ~1+' + 2, 24. с ть !(!85) = (а1+ 1 — 2 )и + с"е<!с Ь 2 = (Ж+ 1)л — (2п — 3)2"т! — 6, где и = (18 М) (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
