/\ /\ /\ /\

087 061 -оо -оо -оо -оо -оо -оо

/\ /\ /\ /\ /\ /\ /\ /\

-оо 087 -оо 061 -оо -оо -оо -оо -оо -оо -оо -оо -оо -оо -оо -оо

.897.

503 275 653 703

/\ /\ /\ /\

087 061 170 -оо 426 509 677 -оо

/\ /\ /\ /\ /\ /\ /\ /\

- оо -оо -оо -оо -оо -оо -оо -оо -оо -оо 154 -оо 612 -оо -оо -оо

12. 2" - 1, один раз для каждого -оо в узле ветвления.

13. Если К > Кг+1, то после шага Н4 можно переходить к шагу Н5 при j = г. (На шаге Н5 ничего не делается, если не выполнено условие Кг < Kr+i; в этом случае на шаге Н6 обязательно произойдет переход к шагу Н8.) Чтобы на протяжении всего алгоритма обеспечить выполнение условия К > Kr+i, можно начать с Kn+i < mm{Ki,..., Kn). Вместо присвоения Rr Hi на шаге Н2 установим Rr+i <~ Rn+i и Rn+i •<- Ri; установим также r2 •«- Rn+1 после того, как выполнится условие г = 1. (Этот прием не ускоряет алгоритм и не укорачивает программу Н.)

14. Чтобы получить простую очередь (или стек), вставляя элемент, приписывайте ему ключ, меньший (соответственно больший) всех ранее присвоенных ключей.

15. Так как преследовалась цель повышения эффективности, следующее решение несколько замысловато; в нем пропускаются все числа, кратные 3 [САСМ 10 (1967), 570].

Р1. Установить р[1] <г- 2, р[2] 3, А; 2, n 5, d (- 2, г 1, t 25 и поместить в приоритетную очередь элемент (25,10,30). (В этом алгоритме р[г] - г-е простое число, к - количество найденных до сих пор простых чисел, п - кандидат в простые числа, d - расстояние до следующего кандидата, г - число элементов в очереди, t = р[г + 2] - следующее значение п, для которого надо увеличить г. Элементы очереди имеют вид {и, v, 6р), где р - наименьший простой делитель и, V - 2р или 4р и U -h и не делится на 3.)

Р2. Пусть {q,q,q") - элемент очереди с наименьшей первой компонентой. Замените его в очереди на (д + q ,q" - q ,q"). (Это означает следующий множитель д"/6, который должен быть исключен.) Если п > q, повторять этот шаг до тех пор, пока не станет п < q.

РЗ. Если п> N, прекратить выполнение алгоритма. В противном случае, если п< q, установить к i- к + 1, р[к] •«- п, п-«-n--d, d-«-6 - dn повторить этот шаг.

Р4. (Теперь n = g - непростое число.) Если тг = t, установить г <-г + 1, и р[г + 2], t <- и вставить в очередь либо (t, 2и, 6и), либо (t, 4u, 6u), если и mod 3 = 2 или и mod 3 = 1 соответственно.

Р5. Установить n<-n + d, d<-6 - dn вернуться к шагу Р2.

Начало вычислений выглядит следующим образом.

Содержимое очереди Найденные простые числа

(25, 10, 30) 5, 7, 11, 13, 17, 19, 23

(35, 20, 30)(49, 28, 42) 29, 31

(49, 28, 42)(55, 10, 30) 37, 41, 43, 47

(55, 10, 30)(77, 14, 42)(121, 22, 66) 53

Если очередь реализована в виде пирамиды, то можно найти все простые числа < ЛГ за 0{N log N) шагов; размер пирамиды не превышает количества простых чисел < y/N. Решето Эратосфена (реализация приведена в упр. 4.5.4-8) - метод с временем вьшолнения порядка 0{N log log N), требующий значительно больше памяти с произвольным доступом. Более эффективные методы реализации будут рассмотрены в разделе 7.1.

16. II. Установить К вставляемый ключ; j <- п + 1.

12. Установить i <- [j/2j.

13. Если г = О или Ki > К, то установить Kj i- К и прекратить выполнение алгоритма.

14. Установить Kj if;, j г и возвратиться к шагу 12.

[В работе Т. Porter, 1. Simon, IEEE IVans. SE-1 (1975), 292-298, показано, что если задана случайная пирамида из равномерно распределенных чисел и An+i - среднее число случаев выполнения шага 4, то получится An = [IgnJ -Ь (1 - п~)А„ при п > 1, где п = (lb/ ib/ 2 ... 60)2 влечет за собой п = (1Ь/ 2 ... 60)2. Если I = [IgnJ, эта величина всегда > Л21+1 1 = (2" - 2)/(2" - 1) и всегда < Ai < а, где а - константа в (19).]

17. Алгоритм Н преобразует массив 1 2 3 в пирамиду 3 2 1, а алгоритм из упр. 16 преобразует его в пирамиду 3 12. [Замечание. Время выполнения этого последнего алгоритма построения пирамиды в наихудшем случае составляет порядка N log N, но эксперименты показали, что для случайного исходного массива шаг 2 во время построения пирамиды выполняется всего около 2.28ЛГ раз. В работе R. Hayward, С. McDiarmid, J. Algorithms 12 (1991), 126-153, строго доказано, что значения постоянных коэффициентов пропорциональности лежат между 2.2778 и 2.2994.]

18. Удалите шаг Н6 и замените операции на шаге Н8 следующими операциями. Н8. [Продвинуться обратно вверх.] Установить j <- i, i <- [j/2\.

Н9. [Подходит ли К?] Если К < Ki или j = I, установить Rj <г- R и возвратиться к шагу Н2. В противном случае установить Rj <- Ri и возвратиться к шагу Н8.

Это, по существу, тот же метод, что и в упр. 16, но с другой начальной точкой в пирамиде. Массив изменяется так же, как в алгоритме Н. Эмпирические проверки этого метода показывают, что число присвоений Rj <- Ri, приходящихся на одну операцию протаскивания в фазе выбора, равно (0,1,2) с вероятностями (.837, .135, .016) соответственно. Этот метод несколько удлиняет программу Н, но повышает асимптотическую скорость до 13NlgN + 0{N). Желательно иметь в системе команд MIX команду деления пополам содержимого индексного регистра.

В работе С. J. Н. McDiarmid, В. А. Reed, J. Algorithms 10 (1989), 352-365, доказано, что при такой модификации сохраняется в среднем (3/3 - 8)ЛГ к 0.232ЛГ сравнений на этапе формирования пирамиды, где /3 определено в ответе к упр. 27. Более углубленный

анализ модификаций Флойда приведен в работе I. Wegener, Theoretical Сотр. Sci. 118 (1993), 81-98.

В работе J. Wu, Н. Zhu, J. Сотр. Sci. и Tech. 9 (1994), 261-266, высказано соображение, что может быть использован и метод двоичного поиска , так что каждая операция протаскивания на фазе выбора будет включать не более Ig ЛГ -)- Ig Ig ЛГ сравнений и Ig ЛГ перемещений записей.

19. Действуйте так же, как в измененном алгоритме протаскивания (упр. 18), установив значения К = Kn, / = 1иг = ЛГ-1с заданного значения j на шаге НЗ.

20. При О < А; < п количество положительных целых чисел < ЛГ, двоичное представление которых имеет вид (Ь„ ... bai... а,)2 при некотором g > О, равно, очевидно, (bk-i ... 60)2 + l + Eo<,<fc2 = (16fc-i...bo)2.

21. Пусть j = (cr ... со)2 принадлежит интервалу [ЛГ/2*+] = (Ь„ ... 6+1)2 < j < [Ьп ... Ьк)2 = [ЛГ/2*]. Тогда Sj равно количеству положительных целых чисел < N, двоичное представление которых - суть (сг •. • coai... а,)2 при определенном g > О, а именно - J2o<q<k 2 = 2*+ - 1. Следовательно, число неособых деревьев размером 2=+i - 1 равно

[ЛГ/2=] - [ЛГ/2*+] - 1 = [(ЛГ - 2=)/2*+j.

[Для вывода последнего тождества воспользуйтесь репликативным законом из упр. 1.2.4-38 при п = 2 и X = ЛГ/2*+\]

22. До того как станет / = 1, пять возможных вариантов таковы: 53412, 35412, 43512, 15432 и 25413. Каждый из этих вариантов 0102030405 приводит к трем перестановкам (0102030405, 0104030205, 0105030402), возможным до того, как получим / = 2.

23. (а) После В итераций имеем j > 2i, следовательно, 21 < г. (Ь) Имеем

ELlog2 {N/1)1 = {[N/21 - L/4J) + 2([iV/4j - [iV/8j) + 3([iV/8J - [N/16J) + • • = 1=1

= [ЛГ/2] + [N/4J + [ЛГ/8] -ь ... = ЛГ - 1/(ЛГ),

где 1(ЛГ) - число единиц в двоичном представлении числа N. Из упр. 1.2.4-42 получаем также Yr=i LS"] = -LS NJ -2"--2. Из теоремы Н известно, что эта верхняя оценка для величины В - наилучшая из возможных на фазе построения пирамиды. Интересно, кроме того, отметить, что существует единственная пирамида из ключей {1,2,..., N}, такая, что в течение всей фазы выбора в алгоритме Н значение К тождественно равняется 1. (При N - 7, например, такой пирамидой будет 7 5 6 2 4 3 1; нетрудно осуществить переход от ЛГ к ЛГ -I-1.) На этой пирамиде и достигается максимальное значение В на фазе выбора пирамидальной сортировки (так же, как и максимальное значение [ЛГ/2] параметра D). Значит, верхняя граница значения параметра В, т. е. наилучшее значение из возможных для всей сортировки, равно ЛГ - i/{N) + N[\g N] - 2-8-1+ + 2.

24. EtilSkY = (N + 1 - 2")n + Eo<fc<nfc2= = {N + l)n - {2n - 3)2"+i - 6, где n = [IgNJ (cm. упр. 4.5.2-22). Следовательно, дисперсия для последнего протаскивания есть /Зл- = ((ЛГ-Ы)- (2п -3)2"+ - б)/ЛГ - ((ЛГ-Ы)п-Ь 2 - 2"+1)7ЛГ2 = 0(1). Стандартное отклонение величины Bn равно iJ2{0s s € Mn}) = 0{\/N).

25. Протаскивание "равномерно" и каждое сравнение Kj-.Kj+i с вероятностью дает результат < . Средний вклад в значение параметра С в этом случае равен в точности половине суммы средних вкладов в значения параметров Аи В, а именно - ((2п-3)2"~ -Ь i)/(2"+-l).