Методические указания и задания к лабораторным работам для учащихся ссуз специальности Т1002



страница16/31
Дата14.08.2018
Размер2.1 Mb.
#43969
ТипМетодические указания
1   ...   12   13   14   15   16   17   18   19   ...   31

Порядок выполнения работы


  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] будут заведомо больше Х.


Бинарный (двоичный) поиск


Данный поиск называется делением пополам (метод дихотомии). Тоже выполняется в упорядоченных массивах, для элементов которого выполняется условие (1). Х- аргумент поиска.

Определяется m=N/2 - целая часть. Рассматривается А[m]-срединный элемент исходной последовательности. Если А[m]=Х, то поиск закончен, он результативен. Если А[m]<Х, то из поиска исключаются все элементы, от А[1] до А[m], т.к. они заведомо меньше Х. Если А[m]>Х, то из поиска исключаются все элементы, от А[m] до А[n]. Поиск продолжается в оставшейся подпоследовательности (половине): определяется значение m-индекс элемента, и если его ключ не равен Х, то из поиска исключаются одна из половинок и т.д.

Пусть дан упорядоченный массив из 10 элементов (N=10):

1 2 3 4 5 6 7 8 9 10

Пусть необходимо в данном массиве найти цифру 6. Определяем m=10/2=5.

Рассматриваем A[5]=5 (А[m]). В данном случае А[m] не равно искомому элементу (5 не равно 6), и проверяем А[m]<Х ? Условие выполняется (5<6) и из поиска исключаются все элементы от 1 до 5. Поиск продолжается в оставшейся половинке.

6 7 8 9 10 (N=5)

Определяем m=5/2=2 (целая часть). Рассматриваем А[2]=7. Так как А[m]>Х (7>6), то из поиска исключаются все элементы от 7 до 10. Поиск продолжается в последовательности элементов, в данном случае состоящей из одного элемента равного 6, который и является аргументом поиска. Поиск закончен.

Описанную процедуру можно представить в виде дерева, в корень которого помещаем срединный элемент всей последовательности, его сыновьями будут срединные элементы половинок. Сыновьями вершин первого уровня будут срединные элементы четвертинок.

Тогда поиск выполняется, начиная с корня. По достижении каждого узла определяется направление дальнейшего поиска. Если аргумент поиска меньше ключа, размещенного в узле, то поиск выполняется в левом поддереве. Если больше , то в правом поддереве. Подобного рода древовидная структура называется деревом поиска.


Пример программы с использованием алгоритма бинарного поиска


Program DemoSearch_2;

Uses Crt;

Const

Maximum=100;{максимальное значение элементов массива}



Type

DataType=Integer;

DataIn=array [1..Maximum] of Integer;{пользовательский тип DataIn, который обозначает массив из элементов типа Integer}

Var


WorkArray:DataIn;{объявляем массив типа DataIn}

i:Byte;


{Объявляем функцию Poisk2, у которой 3 формальных параметра:

1-массив, 2-количество элементов массива, 3-ключ поиска}

Function Poisk2(Vx:DataIn;N:Integer;K1:DataType):Integer;

{Poisk2}


Var

L,U,Middle:Integer;

Rez:Boolean;

j:Integer;

begin

L:=1;


U:=N;

Rez:=False;

While (L<=U) and (not Rez) do

begin


{Средний элемент массива}

Middle:=(L+U)div 2;

{если ключ меньше среднего элемента массива, то поиск происходит в правой оставшейся части массива}

If K1

else

If K1>Vx[Middle] then L:=Middle+1



else

Rez:=True;

end;

If Rez=True then Poisk2:=Middle



else

Poisk2:=0;

end;{Poisk2}

{Основная программа}

Begin

ClrScr;


for i:=1 to 10 do

begin


writeln('Введите ',i,'-й элемент массива');

readln(WorkArray[i]);

end;

Case Poisk2(WorkArray,10,6) of



0:Writeln('Такого значения нет')

else


Writeln('Впервые цифра 6 появилась под номером',Poisk2(WorkArray,10,6));

end;


repeat until keypressed;

End.



Поделитесь с Вашими друзьями:
1   ...   12   13   14   15   16   17   18   19   ...   31




База данных защищена авторским правом ©vossta.ru 2022
обратиться к администрации

    Главная страница