26. (а) (If+ i + l + + li + lf+ 2 + + 1 + Ц + 2 + 1 + 2 + 2 + 3 + 0 + 1 + 1+2 + 1 + 2 + 2 + 3 + 1 + 2 + 2)/26 = 1189/780 и 1.524.

(b) (Ef=iW-+W2J -" + Efc;iniin(afc i,afc-afc-, -l)/(afc-l))/iV, где i(fc) - количество единиц в двоичном представлении числа к, ъ. Ок = (Ibk .60)2- Если

ЛГ = 21 + 2=2 +----h 2, где ei > 62 > • • • > et > О, можно показать, что Е=о() =

((ei + 2)21 + (ег + 4)22 +----\-{et + 2t)2)+t-N. [Асимптотические свойства этой суммы

можно проанализировать при помощи преобразования Меллина; см. Flajolet, Grabner, Kirschenhofer, Prodinger, Tichy, Theoretica.1 Сотр. Sci. 123 (1994), 291-314.]

27. Дж. У. Ренч (мл.) (J. W. Wrench, Jr.) пришел к выводу, что в общем случае ряд Ламберта En>i «"7(1-") можно представить в виде T,n>ii12d\nл)х = Em>i(" + Ek>Л<rn+a~+k)x)xn\

[На случай, когда а„ = 1 и а„ = п, первым обратил внимание И. Г. Ламберт (J. Н. Lambert) в работе Aniage zur Architectonic 2 (Riga, 1771), §875; Клаузен вывел свою формулу для а„ = 1 в работе Crelle 3 (1828), 95, а X. Ф. Шерк (Н. F. Scherk) представил доказательство в Crelle 9 (1832), 162-163. Если а„ = п и х = 5, получим соотношение

1>1

/ /2- + 1\

-AVs-iy "(2m-l)V = 2.74403 38887 59488 36048 02148 91492 27216 43114 + .

Эта константа появляется в приближенных формулах (20), где Bn ~ {/3 - 2)N и Cn ~ {\l5~\a-\)N.\

Кстати, если положить д = хи2 = Х2/в первом тождестве из упр. 5.1.1-16, а затем вычислить щ при 3/ = 1, получим интересное тождество:

п>1 к>1

28. Потомками fc-ro узла являются узлы 3fc-l, SfcnSfc + l; родителем является [(fc + l)/3j. Время выполнения MIX-программы, аналогичной программе Н, асимптотически приближается к 2lN\ogN X IZ.TNlgN машинным циклам. Используя идею из упр. 18, можно сократить его до ISfiVlogjiV х ll.SNlgN, хотя за счет операций деления на 3 добавится большое слагаемое 0(ЛГ).

Более подробную информацию о f-нарных деревьях можно найти в работе S. Окота, Lecture Notes in Сотр. Sci. 88 (1980), 439-451.

30. Предположим, что п = 2 - 1 + г, где t = [IgnJ и 1 < г < 2. Тогда him = [т = 0], и получим

П(п+1)т

<(2-l)h„

(m-j) + 2 *h„(m-t+l) + rhn(m-t) При П > 2,

рассматривая число элементов на уровне j, которые претендуют стать окончательным "пристанищем" для Kn+i после того, как он будет "протянут" на место Ki. Таким образом, если Qnm = hum/2"*, получим

S(n+l)m < е -9n(m-j) + 9n(m-t+l) + Sn(m-t) < (lg(n + 1)) Onm,

ИЗ чего по индукции следует Qnm < Ln = ПГ=2 к-

Среднее суммарное число продвижений во время фазы выбора равно

bn = /liv е "fNm ,

m>0

где hN = Y,m>oNm есть суммарное число возможных пирамид (теорема Н). Известно, что Bn < iVflgiV]. С другой стороны, имеем Bn > т - hjl ЕГ=1(" "~ k)hNk > т -hNLN Er=i("* - > т- 2"+h-LN для всех т. Выбор тп = lg(/iiv/Liv) + 0(1) дает теперь В > lg(/iiv/Liv) + 0(1).

Число сравнений, необходимых для формирования пирамиды, не превышает 2ЛГ, как следует из упр. 23, (Ь), значит, Hn > N\/2. Очевидно, что Ln < (IgiV), и получим lg{hN/LN) > NlgN - NlglgN + 0{N). [J. Algorithms 15 (1993), 76-100.]

31. (Решение предложено Ю. Эдигхоффер (J. EdighofFer), 1981.) Пусть A - массив, содержащий 2п элементов, причем Л[2[г/2]] < A[2i] и Л[2[г72] -1] > Л[2г-1] при 1 < г < п. Кроме того, потребуем, чтобы A[2i - 1] > A[2i] при 1 < г < п. (В соответствии со структурой пирамид последнее условие выполняется для всех г тогда и только тогда, когда оно выполняется при п/2 < г < п.) Эти "пирамиды-близнецы" содержат 2п элементов; если общее число элементов нечетно, то один элемент просто хранится отдельно. Для работы с пирамидами-близнецами можно воспользоваться соответствующими модификациями алгоритмов этого раздела; интересно разработать их во всех деталях. К этой идее независимо пришли и проанализировали ее авторы работы J. van Leeuwen, D. Wood, Сотр. J. 36 (1993), 209-216, в которой такая структура названа интервальной пирамидой.

32. В любой пирамиде из ЛГ различных элементов т - [ЛГ/2] наибольших элементов образуют поддерево. Не менее [m/2j из них должны не быть листьями в этом поддереве, поскольку в двоичном дереве с к листьями имеется, по меньшей мере, к - \ элементов, не являющихся листьями. Таким образом, не менее [m/2J из наибольших т элементов окажутся на первых [ЛГ/2] позициях в пирамиде. Эти элементы должны быть продвинуты на позиции в корне прежде, чем они достигнут своего окончательного положения. Следовательно, доля, вносимая в общее число В путем этого перемещения, составляет не менее Ei=(4lg=J = mlgm--0(m), как следует из упр. 1.2.4-42. Тогда Вшш(ЛГ) >\N\gN + 0{N) + Bmin{lN/2\) и требуемый результат получается индукцией по N. [I. Wegener, Theoretical Сотр. Sci. 118 (1993), 81-98, теорема 5.1. Р. Шаффер, Р. Седгевик и независимо от них Боллобаш (Bollobas), Феннер (Fenner) и Фризе (Frieze) построили перестановки, которые требуют не менее NlgN + 0{NloglogN) продвижений; см. J. Algorithms 15 (1993), 76-100; 20 (1996), 205-217. Такие перестановки довольно редки, как следует из упр. 30.]

33. Пусть Р и Q указывают на данные приоритетные очереди; как и в основном тексте раздела, в следующем ниже алгоритме полагается, что DIST (Л) = О, хотя Л и не является узлом.

Ml. [Начальная установка.] Установить R Л.

М2. [Слияние списков.] Если Q = Л, установить D <- DIST(P) и перейти к МЗ. Если Р = Л, то установить Р <- Q, D •(- DIST(P) и перейти к МЗ. Иначе, если KEY(P) > KEY(Q), установить Т <- RIGHT (Р), RIGHT (Р) -(-R, R<-P, Р-(-Ти повторить шаг М2. Если KEY(P) < KEY(Q), установить Т <- RIGHT(Q), RIGHT(Q) <- R, R -е- Q, Q Т и повторить шаг М2. (Этот шаг, по сути, сливает два "правосторонних списка" данных деревьев, при этом в поля RIGHT временно помещаются указатели вверх.)

МЗ. [Выполнено?] Если R = Л, завершить выполнение алгоритма; Р указывает на ответ.

М4. [Зафиксировать поля DIST.] Установить Q •(- RIGHT (R). Если DIST (LEFT (R)) < D, то установить D <- DIST(LEFT(R)) -Ы, RIGHT(R) •(- LEFT(R), LEFT(R) <- P; иначе -

установить D <- D + 1, RIGHT(R) <- P. Наконец, установить DIST(R) <- D, P <- R, R «- Q и вернуться к шагу МЗ.

34. Начав с рекуррентного соотношения

Lm+l(2) = Lm(2) L(z)- Lfc(z) ,

для составляющих обобщенной производящей функции L{z) = en>o"" = em>l Lm(2),

где Lm{z) = г"*" + • • • порождает левосторонние деревья с кратчайшим путем длиной т от корня до Л, Райнер Кемр (Rainer Kemp) доказал, что L(z) - 2+Х(г)+Е">>1 Lm{zY и что а X 0.25036 и 6 к; 2.7494879 [см. Inf. Ргос. Letters 25 (1987), 227-232; Random Graphs 87 (1990), 103-130]. Луис Трабб Пардо (Luis Trabb Pardo) в 1978 году обратил внимание на то, что производящая функция G{z) = zL{z) удовлетворяет очень изящному отношению G{z) = z + G{zG{z)).

35. Пусть поле DIST исключенного узла равно do, а поле DIST слитых поддеревьев равно dl. Если do = dl, то подниматься вверх вообще не нужно. Если do > di, то затем di = do - 1, и если подняться на п уровней, то новые поля DIST предков узла Р будут равняться соответственно di + 1, di + 2, ..., di + п. Если do < di, восходящий путь должен вести только влево.

36. Вместо обобщенной приоритетной очереди проще всего воспользоваться двусвязным списком; при "использовании" узлов помещайте их в один конец списка, а исключайте - с другого конца. [См. анализ "самоорганизующихся" массивов в разделе 6.1.]

37. В бесконечной пирамиде самый большой к-й элемент с равной вероятностью может оказаться и в правой, и в левой подпирамидах своего большего предка. Таким образом, можно использовать теорию цифровых деревьев поиска и получить е{к) = Ск - Ck-i в обозначениях выражения 6.3-(13). Как следует из упр. 6.3-28, получим е(к) = Igfc + 7/(ln2)+i-q+Jo(fc)+C(fc") ~ lgfc-.274, где а определено в (19), &So{k) - периодическая функция Igfc. [Р. V. Poblete, BIT 33 (1993), 411-412.]

38. Afo = 0; All = {1}; Mn = {N} l±) M.,k i l±) AIv 2i при ЛГ > 1, где fc = [lg(2iV/3)J. РАЗДЕЛ 5.2.4

1. Начните с ii = • • • = н = 1, j = 1. Теперь повторяйте следующие операции: найти min(xiii,..., Xkik) = Xrir и установить Zj = Xri, j j + 1, ir <- V + 1. (B этом случае

будет удобно положить,, что Х;(т + 1) = ОО.)

Если fc не слишком велико, то желательно хранить ключи хц,- ,Хк1 в виде древовидной структуры, которая позволяет осуществлять многократный выбор, как обсуждалось в разделе 5.2.3; тогда потребуется всего [Ig fcj сравнений, чтобы найти каждый новый минимум, кроме первого. На самом деле это типичное применение принципа "наименьший из включенных первым исключается" в приоритетной очереди. Можно хранить ключи в пирамиде и вообще не использовать оо. Дальнейшее обсуждение приводится в разделе 5.4.1.

2. Пусть С - число сравнений; тогда С = т + п - S, где S - количество элементов, передаваемых на шаге М4 или Мб. Как легко видеть, вероятность того, что S > s, равна

rn J + ( n ))/[ Ш )

при 1 < s < m -\- n; Qs = 0 при s > m -Ь n. Следовательно, математическое ожидание величины S есть Цтп = Qi +Я2 + - = т/(п-Ы)--п/(т-Ы) [ср. с упр. 3.4.2-5, 6], адисперсия равна (т„ = (gi +Zq2 + bqi + )-= т(2т--п)/(п-Ы)(п--2)-Ь (т--2п)п/(т-Ы)(т--