Лабораторная работа № 14 Тема: «Исследование основных алгоритмов поиска»
Цель работы – изучить принцип построения алгоритмов поиска.
Теоретические сведения
Алгоритмы поиска, как и алгоритмы сортировки, являются основными алгоритмами обработки данных как системных, так и прикладных задач.
Дан аргумент поиска K. Задача поиска состоит в отыскании записи, имеющей K своим ключом. Существуют две возможности окончания поиска: либо поиск оказался удачным, т.е. позволил определить местонахождение записи, содержащей ключ K, либо он оказался неудачным, т.е. показал, что ни одна из записей не содержит ключ K.
14.1 Последовательный поиск
Для массива, данные в котором не упорядочены путём сортировки или каким-либо другим способом, единственный путь для поиска заданного элемента состоит в сравнении каждого элемента массива с заданным. При совпадении некоторого элемента массива с заданным его позиция в массиве фиксируется. Этот алгоритм называется последовательным или линейным поиском. Эффективность этого метода очень низкая, так как для отыскания одного элемента в массиве размерности N в среднем нужно сделать N/2 сравнений.
14.2 Бинарный (двоичный) поиск
Бинарный или двоичный поиск может быть
использован в качестве алгоритма поиска
в упорядоченном массиве:
Схема алгоритма следующая. Сначала
сравнивают K со средним элементом
массива. Результат сравнения позволяет
определить, в какой половине массива
следует продолжать поиск, применяя к
ней ту же процедуру, и т.д. После не более
чем
сравнений ключ либо будет найден, либо
будет установлено его отсутствие.
14.3 Интерполяционный поиск
По-видимому, бинарный поиск не является
самым лучшим методом поиска, доказательством
чему служит то обстоятельство, что в
повседневной жизни им мало пользуются.
Гораздо чаще используется интерполяционный
поиск. Его схема следующая, Если известно,
что K находится между
и
,
то номер очередного элемента для
сравнения определяется формулой
Последующая процедура аналогична процедуре, используемой в бинарном поиске.
Интерполяционный поиск асимптотически
предпочтительнее бинарного; по существу
один шаг бинарного поиска уменьшает
количество "подозреваемых" записей
от n до
,
а один шаг интерполяционного - от n до
.
В среднем интерполяционный поиск требует
шагов.
Индивидуальные задания
1) Сформировать массив N целых чисел. Создать алгоритм определения суммы чисел, имеющих четные порядковые номера.
2) Сформировать массив N целых чисел. Создать алгоритм определения количества нулевых элементов и исключить их из массива.
3) Сформировать массив N целых чисел. Создать алгоритм определения наличия среди них одинаковых. Нулевые значения не учитывать.
4) Сформировать массив N чисел, среди которых могут быть как положительные, так и отрицательные числа. Создать алгоритм определения суммы и количества только отрицательных значений.
5) Сформировать массив N целых двухзначных чисел. Создать алгоритм выбора чисел, имеющих четные индексы, и записать их в новый массив.
6) Сформировать массив N целых двухзначных чисел. Создать алгоритм выбора чисел, имеющих нечетные индексы, и записать их в новый массив.
7) Сформировать массив N натуральных чисел. Создать алгоритм выбора из них равных и исключить их из массива.
8) Сформировать массив N натуральных чисел. Создать алгоритм выбора всех чисел < 20 или > 80 и исключить их из массива.
9) Сформировать массив N натуральных чисел. Создать алгоритм выбора всех чисел >9 и < 60 и исключить их из массива.
10) Сформировать массив N чисел, среди которых могут быть как положительные, так и отрицательные числа. Создать алгоритм определения суммы положительных и суммы отрицательных чисел.
11) Сформировать массив N целых чисел. Создать алгоритм определения суммы чисел, имеющих четные порядковые номера.
12) Сформировать массив N целых трёхзначных чисел. Создать алгоритм определения всех нечётных чисел и записать их в новый массив.
Контрольные вопросы
1) Что понимается под определением поиска?
2) Какие виды поиска различают?
3) Укажите основные особенности алгоритмов поиска.