2015-06-04
211
1. Изучить теоретические сведения по теме: “Написание программы на Паскале с использованием рекурсии”.
2. Получить индивидуальное задание у преподавателя и разработать программу в соответствии с поставленной задачей.
3. Показать работающую программу преподавателю.
4. Ответить на контрольные вопросы.
Контрольные вопросы
1. Определение рекурсии. Пример программы с использованием рекурсии.
2. Директивы объявления процедур. Косвенная рекурсия.
3. Пример программы с использованием косвенной рекурсии.
Лабораторная работа № 17
Реализация алгоритма бинарного поиска при написании программы на Паскале
Цель работы: формирование знаний и умений по изучению метода бинарного поиска. Приобретение навыков реализации алгоритма бинарного поиска.
Краткие теоретические сведения
Основные понятия и определения
Поиском называется алгоритм, который на входе воспринимает некоторое значение х и определяет запись, ключ которой совпадает со значением х. При этом на выходе такой алгоритм может выдать либо найденную запись, либо указатель на нее. Х называется аргументом поиска.
|
|
|
Если в таблице имеется запись с ключом, равным х, то поиск называется удачным или результативным. В противном случае поиск называется неудачным (безрезультатным).
В дальнейшем будем рассматривать массив А с элементами А[1], А[2] … А[N], в котором индекс изменяется от 1 до N. Кроме того, считаем, что А[i]- и есть ключ i-того элемента массива.
Линейный поиск
Применяется в тех случаях, когда о характере расположения ключей нет никакой информации. Считается, что ключи не упорядочены. Тогда, единственный способ поиска это сравнение Х с А[1]. Если они не равны, тогда Х сравнивается с А[2]. Если Х=А[i], и ключ первичный (каждое его значение уникально в массиве), то поиск прекращается.
Линейный поиск в упорядоченном массиве данных
Пусть для элементов массива А выполняется условие:
A[1]<А[2]<А[3]<…< А[n] (1)
Ключи упорядочены по возрастанию. В произвольном массиве в случае неудачного поиска приходится просматривать массив от начала до конца. В упорядоченном массиве достаточно определить момент выполнения неравенства Х< А[i], после чего поиск следует закончить, т.к. А[i+1] … А[n] будут заведомо больше Х.
