Алгоритмы поиска в фиксированной группе данных

(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