Алгоритмы поиска в фиксированной группе данных
(4 часа)
Цель работы: Освоить на практике алгоритмы поиска элемента в фиксированной группе данных, а также представление фиксированных групп данных; научиться анализировать применяемые алгоритмы поиска.
Домашнее задание:
1. Изучить алгоритмы поиска по ключу в статических массивах: линейный поиск, бинарный поиск.
2. Изучить поиск в таблице, как разновидность поиска в массиве, когда ключ является составным объектом – строкой. Освоить алгоритмы поиска подстроки в строке: прямой, использующий метод деления пополам, алгоритм Кнута, Морриса и Пратта (КМП).
Порядок выполнения работы.
1. Открыть проект Delphi Structures.
2. Добавить в управляющее главное меню пункт «Лабораторная работа №2», при выборе которого должно появляться окно модуля «Poisk» (модуль «Poisk» с формой добавить в проект).
3. Установить на форму модуля Poisk компоненты, обеспечивающие ввод исходных данных, управляющую кнопку (класса TButton или TBitBtn) и компоненты для вывода результатов на экране в соответствии с вариантом задания таблицы №2.1.
4. В обработчике события onClick управляющей кнопки на языке
Object Pascal написать фрагмент программы для реализации алгоритма поиска в соответствии с вариантом.
Отладить обработчик на тестовых примерах и продемонстрировать работу приложения преподавателю.
5. произвести анализ запрограммированного алгоритма (по количеству сравнений).
6. Составить отчет и защитить работу преподавателю. В отчете обязательно представить блок-схему алгоритма решения задачи.
Таблица 2.1
| № вар. | Текст задачи |
| 1. | Дан массив целых чисел х: var x: array [1..20] of 1..21; и объявлен элемент y: y:1..21; Пусть все элементы массива х различны и расположены по убыванию. Используя бинарный поиск, найти y-то единственное целое число y є [1..21], которого нет в этом массиве. |
| 2. | const n=50; var х: array [1..n] of integer; р: integer; Пусть первые (n-1) элемент массива х упорядочены по неубыванию, а n-я позиция в этом массиве свободна. Требуется вставить новый элемент р в этот массив с сохранением упорядоченности по неубыванию. Для поиска места вставки для элемента р использовать бинарный поиск. |
| 3. | const n=31; var x: array[1..n] of integer; p: integer; k:1..n; found: boolean; Дан массив х, элементы которого упорядочены по возрастанию. Для элемента р методом бинарного поиска проверить: если р входит в массив х, то found присвоить TRUE, а переменной к-номер элемента массива х, равного р; если р не входит в массив х, то found присвоить FALSE, а элемент р вставить в массив х, не нарушая порядок возрастания. Замечание: при вводе элементов в массив х последний элемент оставить не заполненным. |
| 4. | const n=10; m=20; var x: array[1..n, 1..m] of integer; y: integer; i,j: integer; В каждом столбце заданной целочисленной матрице, используя прямой поиск по ключу, найти элемент аij ,равный заданному ключу у. Составить массив Z из номеров строк для найденных элементов. Затем прямым поиском определить, присутствует ли в массиве Z элемент zi, равный значению у. |
| 5. | Пусть таблица Т и аргумент поиска х определяются следующим образом: Т: array[0..N-1] of string; x: string; Допустим n велико, а таблица упорядочена в алфавитном порядке. Используя алгоритмы: поиск делением пополам и посимвольного сравнения строк (каждая строка заканчивается #0), запрограммировать поиск х в Т. Если хєТ, выдать совпавшую строку, если х¢Т, то – сообщение о несовпадении х с элементом Тi. |
| 6. | Пусть заданы массивы: S: array[0..N-1] of item; P: array[0..M-1] of item; 0≤M≤N. Методом прямого поиска строки запрограммировать поиск первого вхождения p в S. Item – это символы. Если поиск успешный, то кроме сообщения об этом, вывести номер символа в строке S, с которого начинается найденное совпадение. Проанализировать алгоритм прямого поиска, сделать вывод о худшем случае работы. |
| 7. | С помощью эффективного КМП-алгоритма (Кнута, Морриса и Пратта) запрограммировать поиск образа р в строке S (описание структур р и S в вар. №6). |
Контрольные вопросы
1. Линейный поиск. Условия окончания поиска.
2. Линейный поиск с барьером.
3. Алгоритм поиска делением пополам (двоичный поиск). Анализ алгоритма.
4. Представление строк переменного размера без динамического распределения памяти.
5. Алгоритм поиска строки в таблице строк.
6. Прямой поиск образа в КМП-алгоритме.
7. предтрансляция образа в КМП-алгоритме.
8. Сравнительный анализ алгоритмов поиска образа в строке (по количеству требуемых сравнений).
9. Особенности работы алгоритмов поиска образа в строке, если строка читается из вторичной памяти.
Лабораторная работа № 3