множитель равен \/{р +9)*, нельзя утверждать, что b = 1/(р +9), поскольку количество итераций, необходимых для поиска одних элементов, гораздо больше, чем требуется для поиска других. Это и есть вторая ошибка. (Остерегайтесь подобных ловушек, так как зачастую в теории вероятностей ошибочные утверждения выглядят очень правдоподобно!)

21. Это невозможно, так как метод зависит от величины ключа.

22. FOCS 17 (1976), 173-177. См. также Y. Perl, А. Itai, and Н. Avni, САСМ 21 (1978), 550-554; G. Н. Gonnet, L. D. Rogers, and J. A. George, Acta /n/ormatica 13 (1980), 39-52; G. Louchard, RAIRO Inform. Theor. 17 (1983), 365-385; Computing 46 (1991), 193-222. Отклонение составляет 0(log log Л). Широкомасштабные эмпирические исследования Д. Мар-сальи (G. Marsaglia) и Б. Нарасимхана (В. Narasimhan) [Computers and Math. 26,8 (1993), 31-42] показали, что среднее число обращений к таблице очень близко к Iglg Л, плюс около 0.7 при неудачном поиске. При = 2°, например, для случайного успешного поиска требуется около 4.29 обращений, в то время как для неудачного - около 5.05.

23. При > следует идти вправо, при < - влево; по достижении узла [Т], как следует из (1), выполняется Ki < К < Ki+i и последняя проверка покажет успешность проведенного поиска. (В таблице должен присутствовать ключ Ко = -оо.)

В алгоритме С может быть изменен шаг С2, на котором можно переходить к шагу С4, если выполняется условие К = Ki. На шаге СЗ в случае, если DELTA [j] = О, установите г г - 1 и перейдите к шагу С5. На шаге С4, если DELTA [j] = О, также переходите к шагу С5, который должен выглядеть следующим образом: "При К = Ki алгоритм завершается успешно, в противном случае алгоритм завершается неудачно" (Такое изменение может ускорить программу С только при > 2; среднее время поиска при внесении изменений "уменьшается" с (8.5 Ig - 6)и до (8 Ig + 7)и.)

24. Ключи могут располагаться таким образом, что сначала будет установлено г •<- 1, затем - г •<- 2г или 2г -f 1 в зависимости от того, К < Ki или К > Ki. При i > поиск неудачен. Например, при N = 12 расположение ключей должно быть следующим:

Ка < Ki < Kg < К2 < Кю <Ki< Kn < Ki < К12 < Кб < Кз < Kj.

Время работы такой программы на MIX-компьютере примерно равно 6 Ig единицам. Таким образом, эта программа работает быстрее программы С, однако для начальной установки таблицы требуется известная доля труда и сообразительности.

25. (а) Поскольку ао = 1 - Ьо, fli = 2ао - bi, аг = 2ai - Ьг и т. д., имеем A{z) + B{z) = 1 + 22А(2). Несколько формул, приведенных в разделе 2.3.4.5, можно вывести из этого соотношения, рассматривая А(1), В(1), В(), А(1) и В{1). При использовании двух переменных для того, чтобы отличить шаги влево от шагов вправо, получим более общий результат А{х,у) + В{х,у) = 1 + {х + у)А{х,у), представляющий собой частный случай формулы, справедливой для t-арных деревьев (см. R. М. Кагр, IRE Transactions IT-7 (1961), 27-38).

(b) var {g) = {{N + 1)/N) var (h) - {{N + 1)/N) mean(h) -I- 2.

26. Дерево для трехленточного многофгьзного слияния, соответствующее распределению с заполненным уровнем к, есть дерево Фибоначчи порядка fc -I- 1; надо только поменять правую и левую ветви. (Перерисуйте дерево на рис. 76 из раздела 5.4.4, поменяв местами левые и правые поддеревья А и С При этом должен получиться аналог рис. 8).

27. Поскольку можно упорядочить индексы таким образом, что АГ;, < АГ; < • < Ki, возможно максимум fc -f- 1 исходов из 2*. Таким образом, поиск может быть описан с помощью дерева с узлами, из которых выходит не более (fc-1-l) ветвей. Количество записей, которые могут быть найдены на т-м шаге, - не более fc(fc-f-l)"~. Следовательно, среднее

количество сравнений, как минимум, равно сумме N наименьших элементов мультимножества {кЛ, к{к+ 1)-2, + 1)-3,...}, умноженной на NK При iV > + - 1 среднее количество сравнений > ((fc + 1)" - 1)" Em=i ( + l)"~m >п- 1/fc.

28. [Skrifter udgivne af Videnskabs-Selskabet i Cliristiania, Mathematisk-Naturvidenskabelig Klasse (1910), No. 8; перепечатано в Thues Selected Matliematical Papers (Oslo: Universitetsforlaget, 1977), 273-310]. (a) Tn имеет Fn+i +Fn-i - Fin/Fn листьев. (Это так называемое число Лукаса Ln = Ф" + Ф") (Ь) Аксиома гласит, что Го(Т2(а:)) = Ti{x), и получается Тт{Тп{х)) = T-m+n-i{x) при ТП = 1 ИЛИ п = 1. По индукции ПО п результат справедлив при m = 0; например, Го(Гз(х)) = To{T2{x)*Ti{x)) = To{Ti{T2{x))*To{T2{x))) = Го(Г2(Г2(1))) = Т2(х). И на последнем шаге следует использовать индукцию по т.

29. Пусть Ко = -00 и Kn+i = Kn+2 = оо. Сначала проведем бинарный поиск на множестве АГг < АГ4 < ; это потребует максимум [Ig iVj сравнений. Если поиск неудачен, при этом определяется интервал K2J-2 < К < K2j; К отсутствует, если 2j = N + 2. В противном случае бинарный поиск для K2J-1 определит г, такое, что K2i-2 < K2J-1 < K2i. Теперь может быть два исхода - либо К = K2i-i, либо К отсутствует. (См. Ttieor. Сотр. Sci. 58 (1988), 67.)

30. Пусть п = [N/4\. Начиная с Ki < К2 < < Kn, можно расположить Ki, К3, К2П-1 в любом требуемом порядке, поменяв их местами с любой перестановкой из

К2П+1, К2п+з, .., Kin-i; такое расположение удовлетворяет условиям предыдущего упражнения. Теперь пусть Ki < Кз < < АГ2(+1 з - границы между всеми возможными t-битовыми числами. Вставим K2t+i i, K2t+i+i, ..., Лг++гт-з меясду этим "частоколом" в соответствии со значениями xi, Х2, • • •, Хт- Например, если т - 4, t = 3, xi = (001)2, Х2 = (111)2 и Хз = Х4 = (100)2, требуемый порядок таков:

Ki < Кц <Кз<Кь<К7 < Ki9 < К21 < АГэ < Ки < К13 < Кп.

(Допускается также, чтобы К21 предшествовало Kig.) Бинарный поиск Л2+1+2у-з подмножестве Ki < Кз < < ATji+i-s будет эквивалентен поиску битов числа Xj слева направо. (См. Fiat, Munro, Naor, Schaffer, Schmidt, and Siegel, J. Сотр. Syst. Sci. 43 (1991), 406-424.)

РАЗДЕЛ 6.2.2

1. Используйте головной узел, скажем, с ROOT = RLINK (HEAD); начните выполнять алгоритм с шага Т4 с Р <- HEAD. Шаг Т5 должен выполняться так, как будто К > KEY (HEAD). (Соответственно в программе Т следует заменить команды строк 04 и 05 командами "ENT1 ROOT; СМРА К").

2. На шаге Т5 установите RTAG(Q) <- 1. Кроме того, при вставке влево установите RLINK(Q) <г- Р, при вставке вправо установите RLINK(Q) <- RLINK(P) и RTAG(P) Ч- 0. На шаге Т4 измените проверку "RLINK (Р) ф Л" на "RTAG(P) ф О" (Если узлы вставляются в последовательные ячейки памяти Q и если все удаления осуществляются по принципу LIFO ("последним вошел - первым вышел"), поля RTAG могут быть удалены, поскольку RTAG(P) будет равно 1 тогда и только тогда, когда RLINK (Р) < Р. Подобное примечание справедливо и для левой, и для правой прошивок.)

3. Можно заменить Л корректным адресом и установить KEY (Л) •«- АГ в начале работы алгоритма. В таком случае проверки LLINK и RLINK = Л могут быть удалены из внутреннего цикла. Однако для корректного выполнения вставки необходимо ввести другой указатель, следующий за Р. Это можно сделать, дублировав код так же, как и в программе 6.2. IF. Работа программы при этом не замедляется. Время работы такой модифицированной программы уменьшается до 5.5С единиц.

4. Cn = l + (0-l + l-2 + --- + (n-l)2"-*+Cn i + --- + C;v-i)/iV = + -1 при N >2" - 1. Решением этих уравнений является Cn = 2(Ялг+1 - Яг») + п, Я > 2" - 1. При этом экономится 2Я2П -п-2 « п(1п 4-1) сравнений. Улучшение для п = 1, 2,3,4 составляет соответственно О, g, f, ЩЩ; для малых п выигрыш, как видите, невелик. (См. статью Frazer and McKellar, JACM 17 (1970), 502, в которой подробно описана эквивалентная задача сортировки.)

5. (а) Первым должен быть элемент CAPRICORN; затем умножаем количество способов построения левого поддерева на количество способов построения правого поддерева и на ( 3°), количество совместных перестановок этих двух последовательностей. Таким образом, искомый ответ равен

(В общем случае ответ представляет собой произведение ("Jr") по всем узлам, где I и г означают размеры левого и правого поддеревьев этого узла. Данное произведение равно Л!, деленному на произведение размеров поддеревьев. В результате получилась та же формула, что и в упр. 5.1.4-20; в самом деле, существует очевидное однозначное соответствие между перестановками, позволяющими получить некоторое дерево поиска, и "топологическими" перестановками, подсчитанными в указанном упражнении - при замене а* в дереве поиска на к (с использованием формы записи из упр. 6).) (Ь) 2"* = 1024; на каждом шаге, кроме последнего, должен вставляться либо наименьший, либо наибольший из оставшихся ключей.

6. (а) Для каждой из Рпк перестановок ai... an-idn, стоимость которых равна к, построим п -Ы перестановку ai... a„ ima„, где aj = aj или aj -f-1 в зависимости от выполнения условия aj < т или aj > т (см. раздел 1.2.5, метод 2). Если m = an или an + 1, такая перестановка имеет цену А; + 1; в противном случае ее цена равна к. (Ь) G„(z) = (2z + п - 2)(2z + п - 3)... (2z). Поэтому

Рпк-[ J2 .

Эта производящая функция была получена, в сущности, В. Ч. Линчем (W. С. Lynch) [Сотр. J. 7 (1965), 299-302]. (с) Производящая функция для вероятностей есть gn{z) = Gn{z)/n\. Она является произведением простых производящих функций вероятностей, а потому

vaT(,n) = gvar (±) = g - ) =

2Яп - 4Я< + 2.

(С помощью упр. 6.2.1-25, (Ь) можно вычислить среднее значение и дисперсию Сп, чтобы вычислить дисперсию Сп, которая равна (2 + 10/п)Нп - 4(1 + 1/п){Нп + Н/п) + 4; эта формула выведена Г. Д. Кноттом (G. D. Knott).)

7. Сравнение с к-м наибольшим элементом будет выполнено тогда и только тогда, когда этот элемент появится до т-го и до всех элементов между к- и т-м; вероятность этого равна 1/(т - А; --1). Суммируя по к, получим искомый ответ: Нт + Hn+i-m - 1 [САСМ 12 (1969), 77-80; см. также L. Guibas, Acta Informatica 4 (1975), 293-298].

8. (а) gn{z) = z"- ELi gk-i{z)gn-k{z)/n, go{z) = 1.

(b) 7n - 4(n + 1)Я1 - 2(n-f- 1)Я„ -f- 13n. (B статье P. F. Windley, Сотр. J. 3 (1960), 86, приведены рекуррентные соотношения, по которым можно найти дисперсию численно, однако в ней не содержится решение проблемы. Обратите внимание на отсутствие простой связи с дисперсией Сп, найденной в ответе к упр. 6.)