Алгоритмы поиска. ЗАДАНИЕ. ВАРИАНТЫ ЗАДАНИЙ

Лабораторная работа № 1

Алгоритмы поиска

Цель работы: изучить основные принципы работы алгоритмов поиска, исследовать их свойства:

· алгоритм S (последовательный поиск), в лекциях Better_Linear_Search.

· алгоритм Q (быстрый последовательный поиск), в лекциях Sent_Linear_Search (с использованием last ).

· алгоритм Т (последовательный поиск в упорядоченной таблице), когда в конце таблицы поиска помещается фиктивная запись, значение которой намного больше значения ключа поиска (т.е. в A[n+1]).

· бинарный поиск.

ЗАДАНИЕ

Разработать программы согласно варианту задания.

Провести сопоставительный анализ числа требуемых сравнений во всех алгоритмах как в случае, когда искомая запись находится в массиве, так и при ее отсутствии.

Анализ:

1) по времени выполнения;

2) подсчитать среднее число требуемых сравнений для каждого алгоритма, когда искомая запись находится в массиве и при ее отсутствии, сравнить зависимости среднего количества сравнений в случаях успешного и неуспешного поиска для заданных алгоритмов.

ВАРИАНТЫ ЗАДАНИЙ

№ вар.	Тип ключей	Многократное вхождение
	целые	запрещено
	целые	разрешено
	символьные	запрещено
	символьные	разрешено
	целые	запрещено
	целые	разрешено
	символьные	запрещено
	символьные	разрешено
	целые	запрещено
	целые	разрешено
	символьные	запрещено
	символьные	разрешено

Работу проводить в два этапа:

1. Для массива из 20 элементов (значения массива можно задать при описании массива в самой программе) выполнить поиск по всем четырем алгоритмам для случаев:

· ключ поиска не найден,

· ключ поиска находится в начале массива,

· ключ поиска находится в конце массива,

· ключ поиска находится в середине массива.

На этом этапе необходимо подсчитывать только число требуемых сравнений. Проверяется корректное выполнение алгоритмов поиска.

2. Для массива размерностью больше 10000 элементов (каждый выбирает сам окончательное значение) анализ алгоритмов проводить с помощью получаемых временных характеристик. Здесь же подсчитать среднее число требуемых сравнений для каждого алгоритма, когда искомая запись находится в массиве и при ее отсутствии, сравнить зависимости среднего количества сравнений в случаях успешного и неуспешного поиска.

Отчет по лабораторной работе должен содержать:

· задание;

· структурные схемы алгоритмов;

· тексты программ;

· результаты работы программ и результаты сопоставительного анализа – в виде таблицы;

· выводы по работе.