Нетрадиционное использование подпрограмм. Косвенная рекурсия

В Турбо Паскале есть случаи нетрадиционного объявления подпрограмм, когда в объявлении процедуры содержится директива interrupt (прерывание), external (внешняя) или inline (встроенная) или вместо блока в объявлении процедуры или функции написано forward (опережающая).

Interrupt (прерывание). Объявление процедуры может содержать директиву interrupt перед блоком, и тогда процедура рассматривается как процедура прерывания. Прерыванием называется временное прекращение процесса, вызванное событием, внешним по отношению к этому процессу. Необходимость в процедурах прерывания возникает, когда программист решает определить собственные алгоритмы реакции на прерывание операционной системы, отменив при этом стандартные реакции. Процедуры прерывания нельзя вызывать с помощью операторов процедур и что каждая процедура прерывания должна задавать список параметров так:

procedure MyInt(Flags, CS, IP, AX, BX, CX, DX, SI, DI, DS, ES, BP:Word);interrupt;

где CS, IP, AX, BX, CX, DX, SI, DI, DS, ES, BP — регистры процессора.

Внешние объявления (external). Внешние объявления позволяют связывать отдельно скомпилированные процедуры и функции, написанные на языке ассемблера. С помощью директивы {$L имя файла} внешнюю программу можно связать с программой или модулем, написанным на Паскале. Пример объявления внешней процедуры:

procedure MoveWord(var Source, Dest; Count: Word); external;

В тексте программы при объявлении внешних подпрограмм нужно задать директиву компилятору $L, аргументом которой является имя OBJ-файла, содержащего код подключаемой подпрограммы, например: {$L BLOCK. OBJ}

Inline (встроенная). Директива inline позволяет записывать инструкции в машинном коде, не используя блок операторов. При вызове обычной процедуры компилятор создает код, в котором параметры процедуры помещаются в стек, а затем для вызова процедуры генерируется инструкция call. Когда вызывается внутренняя процедура, компилятор генерирует код из директивы inline вместо call. Таким образом, inline-процедура "расширяется" при каждом обращении к ней аналогично макрокоманде на языке ассемблера. (Макрокоманда - macro- предложение языка программирования, вместо которого компилятор при трансляции записывает несколько машинных команд.)

Опережающие объявления (forward). Помимо прямых рекурсий, рассмотренных ранее, рекурсивный вызов может быть и косвенным, т. е. одна процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую процедуру. А так как до вызова процедуры она обязательно должна быть описана, то используется опережающее объявление: процедура содержит описание только своего заголовка, вслед за которым ставится зарезервированное слово forward (опережающий), а описание текста процедуры помещается далее в тексте программы гуже без повторения описания списка формальных параметров и называется определяющим объявлением.

Опережающее объявление и определяющее объявление должны находиться в одной и той же части объявления процедур и функций. Между ними могут быть объявлены другие процедуры и функции, и они могут вызывать процедуру с опережающим объявлением. Таким образом, возможна взаимная рекурсия. Определяющее объявление процедуры может быть external или assembler. Однако оно не может быть near-; far-; inline- или другим forward-объявлением. Определяющее объявление также не может содержать директивы interrupt, near или far. Опережающие объявления не допускаются в интерфейсной части модуля.

Примером программы с использованием вложенных подпрограмм-процедур может быть программа Demo_Tower, в которой реализован алгоритм древней игры "Ханойские башни". Имеются три стержня, на одном из них (например, на левом) засажены диски разных размеров, причем диски располагаются так, чтобы стержень с дисками напоминал башню, т. е. внизу располагаются самые большие диски, а вверху маленькие. Цель игры- перенести башню с правого стержня на левый, причем за один раз можно переносить только один диск и при этом можно насаживать только диск с меньшим диаметром на диск с большим диаметром. Средний стержень является вспомогательным для временного хранения дисков.

program Demo_Tower; {Ханойские башни- перенести кольца с правого стержня - 3 на левый - 1}

Type

Position = (Left, Centre, Right);

var

N: integer;

procedure MoveDisk(From, Tol: Position); {Перемещение диска}

procedure WritePos(P: Position); {процедура WritePos внутри процедуры MoveDisk}

begin

case P of

Left: Write('1');

Centre: Write('2');

Right: Write('3');

end;

end;

begin {начало процедуры MoveDisk}

WritePos(From);

Write(': ');

WritePos(Tol);

Writein;

end;

procedure MoveTower(Hight:integer;From,Tol,Work:position);

begin

if Hight>0 then

begin

{Рекурсивный вызов}

MoveTower(Hight-1,From,Work,Tol);

MoveDisk(From,Tol);

{Рекурсивный вызов}

MoveTower(Hight-1,Work,Тоl, From);

end;

end;

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

Writeln('Введите число колец: ');

Readln(N);

MoveTower(N,Right,Left,Centre); {Вызов процедуры с передачей ей фактических параметров}

end.

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

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<Vx[Middle] then U:=Middle-1

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. Изучить теоретические сведения по теме “Алгоритм бинарного поиска”.

2. Получить у преподавателя индивидуальное задание и разработать программу по заданному варианту.

3. Показать работающую программу преподавателю.

4. Ответить на контрольные вопросы.

Контрольные вопросы

1. Основные понятия поиска данных.

2. Различные методы поиска данных. Краткое описание алгоритмов.

3. Бинарный поиск. Описание алгоритма и пример программы.

 

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