Поиск Фибоначчи изобретен Дэвидом Э. Фергюсоном (David Е. Ferguson) [САСМ 3 (1960), 648]. Бинарные деревья, подобные деревьям Фибоначчи, появились в "пионерской" работе норвежского математика Акселя Тью (Axel Thue) еще в 1910 году (см. упр. 28). Деревья Фибоначчи без меток появились также в качестве курьеза в популярной книге Хьюго Штейнгауза (Hugo Steinhaus) Mathematical Snapshots (New York: Stechert, 1938, c. 28). Они изображались корнем вниз и выглядели почти как настоящие деревья, с правыми ветвями, которые были в два раза длиннее левых (так что все листья находились на одном уровне).

Интерполяционный поиск был предложен В. В. Петерсоном (W. W. Peterson) [IBM J. Res. к Devel. 1 (1957), 131-132], однако корректный анализ этого метода был сделан значительно позже (см. упр. 22).

УПРАЖНЕНИЯ

► 1. [21] Докажите, что если на шаге В2 бинарного поиска и< I, то и = 1 - 1и Ки < К < Ki. (Полагаем, что Ко = -оо и Kn+i = -f-oo, хотя эти искусственно введенные ключи в действительности алгоритмом не используются и не обязаны находиться в таблице.)

► 2. [22] Будет ли алгоритм В продолжать корректно работать при наличии К в таблице, если мы: (а) установим на шаге В5 "I ч- г" вместо "I ч- г + 1"; (Ь) установим на шаге В4 "и <- г" вместо "и ч- г - 1"; (с) внесем оба эти изменения?

3. [15] Какой метод поиска соответствует дереву (~) ?

Каково среднее число сравнений выполняется при успешном и неудачном поиске?

4. [20] Если поиск с использованием программы 6.IS (последовательный поиск) выполняется ровно 638 единиц времени, то как долго будет работать программа В (бинарный поиск)?

5. [М24] Для каких значений N программа В в среднем выполняется леленнее последовательного поиска (программа 6.1Q) в случае успешного поиска?

6. [28] (К. Ю. Айверсон (К. Е. Iverson).) Упр. 5 приводит нас к мысли, что стоит иметь некий гибридный метод, переходящий от бинарного поиска к последовательному при достаточном уменьшении интервала поиска. Напишите соответствующую программу для MIX-компьютера и определите наилучший момент перемены метода поиска.

► 7. [М22] Будет ли алгоритм U корректно работать, если мы изменим шаг U1 так, что

a) и i, н т установятся равными [A/2J;

b) и г, и m установятся равными rN/2l?

[Указание. Предположите, что первый шаг был "Установить i i- О, тп <- N (или N + 1), перейти к шагу U4".]

8. [М20] Пусть dj = DELTA [j] является j-м приращением в алгоритме С, как определено в (6).

a) Чему равна сумма Ejlfo" <5j?

b) Чему равны минимальное и максимальное значения г, которые могут появиться на шаге С2?

9. [20] Существует ли значение N > 1, при котором алгоритмы В и С в точности эквивалентны в том смысле, что они оба выполняют одну и ту же последовательность сравнений для всех аргументов поиска?

10. [21] Поясните, как написать MIX-программу для алгоритма С, которая будет содер-нсать около 71giV инструкций и выполняться примерно за 4.51giV единиц времени.

11. [М26] Найдите формулы зависимости средних значений Cl, С2 ч А от N и S в частотном анализе программы С.

12. [20] Изобразите дерево бинарного поиска, соответствующее методу Шара при N = 12.

13. [М24] Протабулируйте средние значения количества сравнений в методе Шара для 1 < iV < 16, рассматривая случаи как успешного, так и неудачного поиска.

14. [21] Поясните, как распространить алгоритм F на все значения N >1.

15. [М19] Для каких значений к дерево Фибоначчи порядка к определяет оптимальную процедуру поиска (имеется в виду наименьшее среднее количество выполняемых сравнений)?

16. [21] На рис. 9 показана диаграмма размножения кроликов в исходной задаче Фибоначчи (см. раздел 1.2.8). Существует ли простая взаимосвязь между .этой диаграммой и обсуждавшимся в разделе деревом Фибоначчи?

Первоначальная пара . Первый месяц . Второй месяц . Третий месяц Четвертый месяц -Пятый месяц -Шестой месяц

Рис. 9. Пары кроликов, размножающиеся в соответствии с правилом Фибоначчи.

17. [М21] Из упр. 1.2.8-34 или 5.4.2-10 известно, что каждое натуральное число п единственным образом представляется в виде суммы чисел Фибоначчи п = Fai -f-Р02 + + Por > где г > 1, Oj > Oj+i -Ь 2 при 1 < j < г и Ог > 2. Докажите, что в дереве Фибоначчи порядка к путь от корня до узла (п) имеет длину -)-1 - г - Ог.

18. [МЗО] Найдите точные формулы зависимостей средних значений С\, С2 и А от к, Fk, Fk+i и S при частотном анализе программы F.

19. [М42] Проведите детальный анализ среднего времени работы алгоритма, предложенного в упр. 14.

20. [М22] Количество сравнений, выполняемых при бинарном поиске, приблизительно равно logj N, а при поиске Фибоначчи - (ф/у/Е) log N. Цель этого упражнения - показать, что данные формулы представляют собой частные случаи более общего результата.

Пусть р и q - положительные числа и р + q = 1. Рассмотрим алгоритм поиска в таблице из N чисел в порядке возрастания. Алгоритм начинается со сравнения аргумента с (piV)-M ключом и затем повторяет эту процедуру с меньшими блоками, выбираемыми исходя из результатов сравнения. (Бинарный поиск соответствует р = q = 1/2; поиск Фибоначчи - р = 1/ф, q = 1/ф.)

Обозначим среднее количество сравнений, необходимых для поиска в таблице размером N через C(N). Оно приближенно удовлетворяет следующим соотношениям:

С(1) = 0; CiN) = l+pC(pN) + qC{qN) для N > 1.

Это можно объяснить тем, что после сравнения поиск сводится примерно с вероятностью р к поиску среди pN элементов и с вероятностью q - к поиску среди qN элементов. При

больших N мы можем пренебречь эффектами, связанными с тем, что pN и qN - не целые числа,

a) Покажите, что C{N) = log N удовлетворяет приведенным соотношениям при некотором Ъ (для бинарного поиска и поиска Фибоначчи величина b согласуется с приведенными формулами).

b) Рассмотрим следующее рассуждение: "С вероятностью р интервал поиска делится на 1/р и с вероятностью q - на Таким образом, интервал в среднем делится на р (1/р) -f- 5 • (1/5) = 2, т. е. алгоритм при любых р и 5 одинаково хорош, в точности как и алгоритм бинарного поиска" Содержится ли в приведенном рассуждении ошибка?

21. [20] Изобразите бинарное дерево для интерполяционного поиска при N = 10.

22. [M4I] (Э. Ч. Яо (А. С. Yao) и Ф. Ф. Яо (F. F. Yao).) Покажите, что корректно реализованный интерполяционный поиск асимптотически требует в среднем Ig Ig N сравнений в случае N рассортированных независимых равномерно распределенных ключей. Более того, все алгоритмы поиска в таких таблицах должны в среднем выполнять Ig Ig N сравнений (асимптотическая оценка).

► 23. [25] Алгоритм бинарного поиска Боттенбрука, упоминавшийся в конце этого раздела, позволяет избегать проверок равенства до конца поиска (при работе алгоритма нам известно, что Ki < К < Ku+i и проверка равенства не проводится до тех пор, пока не будет выполнено условие I = и). Такой трюк мог бы немного ускорить работу программы В для больших N, так как команда JE была бы удалена из внутреннего цикла. (Данная идея почти не реальна в связи с тем, что IgiV обычно достаточно мал, а дополнительная итерация в нашей программе компенсируется только при N > 2 для успешного поиска, так как время работы "уменьшается" с (18IgiV - 16)м до (17.5lgiV -)- 17)и!)

Покажите, что любой алгоритм поиска, соответствующий бинарному дереву и использующий тройное ветвление во внутренних узлах ( < , = или > ), может быть преобразован в алгоритм с двойным ветвлением (< или >). В частности, покажите, каким образом можно модифицировать алгоритм С.

► 24. [23] В разделах 2.3.4.5 и 5.2.3 мы видели, что полное бинарное дерево является удобным способом представления дерева с минимальной длиной пути в последовательных ячейках. Разработайте эффективный метод поиска, основанный на таком представлении. [Указание. Можно ли в бинарном поиске использовать вместо деления на 2 умножение на 2?]

► 25. [М25] Предположим, что бинарное дерево имеет о* внутренних и Ьк внешних узлов на уровне к {к - 0,1,...; корень находится на нулевом уровне). Так, на рис. 8 имеем (ао, ai,..., as") = (1,2,4,4,1,0) и (Ьо, bi,..., 65) = (О, О, О, 4, 7, 2).

a) Покажите, что существует простое алгебраическое соотношение между производящими функциями A{z) = Xjj, аг* и В(г) = bkZ.

b) Распределение вероятностей для успешного поиска в бинарном дереве имеет производящую функцию g{z) = гА(г)/Л, а для неудачного - h{z) = B(z)/(N+l). (Учитывая используемые в разделе обозначения, можно записать: Cn = mean(p), Cn = mean(/i); выражение (2) связывает эти величины.) Найдите зависимость между var(p) и var(/i).

26. [22] Покажите, что деревья Фибоначчи связаны с сортировкой методом многофазного слияния на трех лентах.

27. [МЗО] (Г. С. Стоун (Н. S. Stone) и Джон Лини (John Linn).) Рассмотрим процесс поиска, в котором одновременно используется к процессоров и который базируется на сравнении ключей. На каждом шаге поиска определяется к индексов - ii,...,ik - и выполняется к одновременных сравнений. Если для некоторого j выполняется К = Ki, поиск завершается успешно. В противном случае мы переходим к следующему шагу, основанному на 2* возможных исходах сравнений: К < Kij или К > Ki-, 1 < j < к.