Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 16
Текст из файла (страница 16)
[26] Существует лн значение а? > 1, при котором алгоритмы В и С в точности эквивалентны в том смысле, чта ани аба выполняют аллу н ту же последовательность сравнений для всех аргументов поиска? 10. [21] Поясните, как написать й11-программу для алгоритма С, которая будет содер. жать около 7 1б Л инструкций я выполняться примерно за 4.5 12 Х единиц времени.
11, [Мйб) Найдите формулы зависимости средних значений С1, С2 и А от А' н 2 в частотном анализе программы С. 12, [20] Изобразите дерево бинарного поиска, соответствующее методу Шара при?т' = 12. 13. [М24) Протабулируйте средние значения количества сравнений в методе Шара для 1 < М < 16, рассматривая случаи как успешного, так и неудачного поиска. 14. [21) Поясните, как расщюстранять алгоритм Р на все значения 1т' > 1. 15. [М19) Для каких значений й дерево Фибоначчи порядка й определяет оптимальную процедуру поиска (имеетсл в виду наименьшее среднее количество выполняемых сравнений)? 16. [21) На рис.
9 показана диаграмма размножения кроликов в исходной задаче Фнбоначчи (см. раздел 1.2.6). Существует ли простая взаимосвязь между. этой диаграммой и обсуждавшимся в разделе деревом Фибоначчи? Первояачельяая лара Первый месяц Второй месяц Третий месяц Четвертый месяц Пятый месяц Шестой месяц Рис. й. Пары кроликов, размножающиеся в соответствии с правилом Фнбоначчи. 17. [М21) Из упр. 1.2.8-34 или 5.4,2 — 10 известно, что каждое натуральное число и единственным образом представляется в виде суммы чисел Фибоначчи и = р;, + Г„+. + Е,„, где г > 1, а, > а +~+2 при 1 <1 с г на, > 2, Докажите, что в дереве Фибоначчи порядка Й путь от корня до узла ® имеет длину й + 1 — г — а,. 16.
[МУ0) Найдите точные формулы зависимостей средних значений С1, С2 и А от й, Ре, Реет и о при частотном анализе программы Р. 19. [М42] Проведиге детальный анализ среднего времени работы алгоритма, предложенного в упр. 14. 20. [М22] Количество сравнений, выполняемых при бинарном поиске, приблизительно равно 1ок А', а при поиске Фибоначчи -- (4/т/5 )!обе Х Цель этого упражнения — пока зать, что данные формулы представляют собой частные случаи более общего результата.
Пусть р и о — — положительные числа и р+ д = 1, Рассмотрньт алгоритм поиска в таблице из 1т' чисел в порядке возрастания, Алгоритм начинается со сравнения аргумента с (рА?)-м ключом и затем повторяет зту процедуру с меньшими блоками, выбираемыми исходя из результатов сравнения. (Бинарный поисх соответствует р = 4 = 1/2; поиск Фибоначчи — р = 1/й 2 = 1/р ) Обозначим среднее количество сравнений, необходимых лля поиска в таблице размером 1т' через С(Ат). Оно приближенно удовлетворяет следующим соотношениям: С(1) = 0; С(А') = 1+ рС(рА?) + 4С(4А') для 1т > 1. Это можно обьяснить тем, что после сравнения поиск сводится примерно с вероятностью р к поиску среди рА' элементов и с вероятностью 4 — к поиску среди дМ элементов.
При болыпих Х мы можем пренебречь эффектами, связанными с тем, что РА» и»7А» — не целые числа. а) Покажите, что С(М) = 1об„д» удовлетворяет приведеиным соотношениям при некотором Ь (для бинарного поиска и поиска Фибоначчи величина Ь согласуется с приведенными формулами). Ь) Рассмотрим следующее рассуждение: "С вероятностью р интервал поиска делится на 1/р и с вероятностью д — на 1/Ф Таким образолп интервал в средием делится на р. (1/р) +»7 (1/»7) = 2, т. е. алгоритм при любых р и»7 одинаково хорош, в точности как и алгоритм бинарного поискГ Содерл»итси ли в приведенном рассуждении ошибка? 21.
(20) Изобразите бииарное дерево для интерпаляциоииого поиска при А» = 10. 22. (М41) (Э. Ч. Яо (А. С. Ъао) и Ф. Ф. Яо (Г. Р. Ъао).) Покажите, что корректно реализованиый интерполяпионный поиск асимптотически требует в среднем 18 18 Х сравнений в случае А» рассортированных независимых равномерно распределенных ключей. Более того, есе алгоритмы поиска в таких таблицах должны в среднем выполнять 18 18 А» сравнений (асимптотическая оцекка). ь 23. (Зб) Алгоритм бинарного поиска Боттенбрука, упоминавшийся в коице этого раздела, позволяет избегать проверок равенства до конца поиска (при работе алгоритма нам известно, что К» < К < К„+» и проверка равенства ие проводится до тех пор, пока не будет выполнено условие 1 = и).
Такой трюк мог бы иемиого ускорить работу программы В для больших А»,так как команда 38 была бы удалена из виутреинего цикла. (Данная идея почти не реальиа в связи с тем, что 18 А» обычно достаточно мвл, а дополнительная итерация в нашей программе компенсируется только при А» > 2 для успешного поиска, так как время работы "уменьшаетсв" с (1818А» — 16)и до (17.518%+ 17)и!) Покажите, что яю6ой алгоритм поиска, соответствующий бинарному дереву и использующий тройное ветвлеиие во внутренних узлах ( <, = или > ), может быть преобразован в алгоритм с двойным ветвяением (< или >). В частности, покажите, каким образом можно модифицировать алгоритм С.
ь 24. [Йу) В разделах 2.3.4.5 и 5,2,3 мы видели, что полиое бииариое дерево является удобным способом представления дерева с минимальной длииой пути в последовательных ячейках. Разработайте эффективный метод поиска, основаняый яа таком представлении. (Указание. Можно ли в бииарпом поиске испольэовать вместо деления на 2 умножение ца 2?] ° 26. (Мйб) Предположим, что бинарное дерево имеет аь внутренних и Ьь виешних узлов на уровне Ь (Ь = 0,1,...; корень находится на нулевом уровне). Так, иа рис. 8 имеем (оо,а»,,аз) = (1,2,4,4,1,0) и (Ьо,Ь»,...,Ь») = (0,0,0,4,7,2). а) Покажите, что существует простое алгебраическое соотшнпение меж»О' производил»ими функциями А(э) = 2 аьзь и В(з) = 2 „Ььз~. Ь) Распределение вероятностей для успешыого поиска в бинарном дереве имеет производящу»о функцию р(з) = зА(з)/А», а для иеудачиого — Й(г) = В(з)/(А»+1).
(Учитывая используемые в разделе обозначения, можно записать: Ся = шеап(д), Сл = шеап(Л); выражение (2) связывает зти величииы.) Найдите зваисимость между гаг(р) и кчи(Ь). 26. (82) Покажите, что деревья Фибоиаччи связаны с сортировкой методом миогофазного слияния на трех лентах. 27. (Мйй) (Г. С. Стоун (Н. 8. 5»опе) и Джон Линн (Лойп 1,1пп).) Рассмотрим процесс поиска, в котором одиовремеяно используется Ь процессоров и который базируется на сравиении ключей. На каждом шаге поиска определяется Ь индексов — П,,,,,»ь — и выполияется Й одповремеиных сравнеиий. Если для некоторого у выполняется К = К», поиск завершается успешио. В противном случае мы переходим к следующему шагу, основанному на 2" возможных исходах сравнений: К < К, или К > КО, 1 < у < Й. Докажите„что такой процесс при К -р ао должен выполнять в среднем минимум !оя„, Х шагов (в предположении, что все ключи таблицы, как и аргумент поиска, рав- новероятны).
(Следовательно, выигрыш от использования й процессоров составляет не х раз, как может показаться, а только !О(й+ 1) раэ; в этом смысле выгоднее выполнять поиск с помощью одного отдельного процессора, не кооперируя их.) 28. [МЙЮ] Определим дерево Тыо (Тбне) Т прн помощи алгебраического выражения с использованием бинарного оператора "р" следующим образом: То(х) = х р х, Т1(х) = х, Тр+э(х) = Т„+г(х) р Т„(х). а) Количество листьев дерева Т„ранна количеству х в полной записи Т (х).
Выразите его при помощи чисел Фибоначчи, Ь) Докажите, что если бинарный оператор "р" удовлетворяет аксиоме ((хрх) рх) р((хрх) рх) =х, то Т (Т„(х)) = Т .„„ ~(х) лля всех тв > О и н > 1. ь 29. [22] (Поль Фельдман (Рав! Ге!Ошап), 1985.) Вместо предположения, что К1 < Кэ < " < Кн, допустим, чта Кн Н < Крпл « Кр!д р где перестановка р(1)р(2)...Р(Ж) является инваюоциейр и р(з) = 2 для всех четных значений 2, Покажите, что можно найти любой данный ключ К нли выяснить, что он отсутсъвует, проведя максимум 2[!я Х] + 1 сравнений. ЗО.
[22] (инеолюиионное ходнроеание.) используя идеи предыдущего упражнения, расположите гт ключЕй таким образом, чтобы их относительный порядок неявно кодировал произвольно взятый массне ьбитовых чисел хь хэ, ..., х; щ < М/4+ 1 — 2'. Найденный вами способ расположения должен позволять определять первые )р бнт числа х. при помощи Й сравнений для любого у, а также находить произвольный ключ при помощи < 2 [!я М] + 1 сравнений. (Этот результат используется в теоретическом изучении структур данных, асимптотически эффективных во времени н пространстве.) б.2.2. Поиск по бинарному дереву В предыдущем разделе мы видели, чта неявная структура бннарнага дерева облегчает понимание бинарного поиска и поиска Фнбаначчи.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
