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

В Турбо Паскале есть случаи нетрадиционного объявления подпрограмм, когда в объявлении процедуры содержится директива 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-того элемента массива.