Учебное пособие Самара 2015 + 004. 43 Ббк 32. 973 Н 19
Download 1.98 Mb.
|
Lekcii AiSD 2015
|
Моиск с использованием чисел Фибоначчи
Ряд чисел Фибоначчи определяется как F( п) —— F(n— 1) + F(n—2), F(0) = 0, F( l) = 1, F(2) = 1, (12.2)
F —— 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . Числа Фибоначчи используются вместо степеней двойки при делении интервала. В данном случае вместо деления используются только сложение и вычитание. Для этого требуется таблица чисел Фибоначчи, или процедура их вы- числения, исходя из длины интервала. Данный метод проще реа- лизуется при размере массива, на 1 меньше очередного числа Фибоначчи N + 1 = F . 12.3. Специальные виды поиска Мнтерполяционный поиск произошел от естественного поиска данных в упорядоченном массиве человеком. Если из- вестно, что искомый ключ k находится между некоторым «ниж- ним» ключом k и некоторым «верхним» ключом +h: (12.3) то следующее сравнение делается на расстоянии (I — h)( k — i ! h I (12.4) от текущей позиции k,. Предполагается что данные в массиве возрастают в арифметической прогрессии. Именно по такому алгоритму выполняется поиск нужной карточки в "бумажном" библиотечном каталоге, или страницы в книге. Этот алгоритм эффективнее бинарного поиска только в слу- чае арифметической прогрессии, так как на каждом шаге умень- шает интервал анализа не до п/2 а до in, и требует в среднем око- 163 лО log2(log2 V шагов, если упорядоченные данные имеют рав- номерное распределение. Недостаток этого алгоритма — затраты времени на дополни- тельные операции при внутреннем поиске. Разница между lOg2(lOg2 *'7) Й log2 *'Ј становится весьма существенной при бoльтнx N, а типичные наборы данных (которыми для этого по- иска часто являются файлы) обычно считаются недостаточно случайными. Этот алгоритм может быть достаточно успешным при поис- ке во внешних запоминающих устройствах. Ещё один специальный случай поиска — это поиск вхожде- ния некоторой подстроки в строку. Для поиска подстроки в строке могут использоваться алгоритмы Бойера—Мура (п его не- сколько модификаций) и Кнута—Морриса—Мратта. Вопросы н задания для самоконтроля Что такое поиск? Что называется ключом поиска? Какие известны методы поиска? К каким структурам данных может применяться опе- рация поиска? Какой из основных алгоритмов поиска является наибо- лее эффективным? Какое требование предъявляется к структуре данных, в которой выполняется двоичный поиск? Чем отличается поиск в массиве от поиска в списке? Чем отличаются процедуры поиска в односвязном и двусвязном списках? В чем заключается метод линейного поиска? В чем заключается метод двоичного поиска? Почему двоичный поиск получил такое название? Какие известны варианты двоичного поиска? Пригоден ли двоичный метод для поиска данных в неупорядоченной структуре? Какой из методов поиска данных в массиве является более универсальным? 164 Существуют ли какие-нибудь недостатки у линейного поиска? Если да, то какие? Какова трудоёмкость линейного поиска? Перечислите особенности последовательного поиска. В каких случаях применяется последовательный по- иск? Перечислите достоинства и недостатки последова- тельного поиска. Соблюдение какого условия необходимо для приме- нения к структуре данных двоичного поиска? Какими достоинствами обладает двоичный поиск? Какова трудоёмкость двоичного поиска? Предложите эффективный алгоритм поиска в массиве упорядоченных неуникальных данных. 165
Чтобы воспользоваться эффективными алгоритмами поиска, данные должны быть упорядочены в том или ином порядке, ина- че говоря, отсортированы. Сортировка (или упорядочение), также как и поиск, является одной из часто используемых при обработке данных операций и применяется ко многим структурам данных: массивам, связным спискам, деревьям и графам. Существуют свидетельства, что первой программой для ЭВМ с хранимой программой (с архитектурой Джона фон Ней- мана) была именно программа сортировки [8]. Download 1.98 Mb. Do'stlaringiz bilan baham: 
|