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