Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема: Разработка рекурсивных алгоритмов и программ
Цель работы: Сформировать знания и умения по работе с подпрограммами. Приобрести навыки написания программ с использованием рекурсивных процедур и функций.
Время выполнения: 2 часа
Порядок выполнения работы:
Теоретические сведения
Рекурсия — это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе.
Примером программы с использованием рекурсии может быть программа вычисления факториала числа. Факториалом натурального числа n называют произведение чисел 1*2*...*n.
{Вычисление факториала числа п с использованием рекурсивной функции}
program Demo_Rekurs;
var N : integer;
F : longint;
{Описание функции, N — формальный параметр-значение типа integer, результат выполнения функции типа longint}.
function Fakt(N : integer): longint;
begin {Начало вычисления функции}
if N=1 then Fakt:=1 {Проверка условия завершения рекурсии}
else Fakt:=N*Fakt(N-1); {Рекурсивное вычисление N!}
end;
begin {Начало главной программы}
Writeln('Введите число N : ') ;
Read(N) ;
F:=Fakt(N); {Вызов функции для фактического параметра N}
Writeln('Для числа ',N,' значение факториала= ', F);
end.
После запуска программы на экран выводится запрос: "Введите число N: ", затем с клавиатуры считывается значение целого числа N и в выражении F:=Fakt(N) вызывается функция Fakt с параметром-значением N. В подпрограмме-функции вычисления факториала проверяется условие N=1. Если оно выполняется, то функции Fakt присваивается значение 1, на этом выполнение подпрограммы-функции завершается. Если условие N=1 не соблюдается, то выполняется вычисление произведения N*Fakt(N-1). Вычисление произведения носит рекурсивный характер, так как при этом осуществляется вызов функции Fakt(N-1), значение которой вычисляется, в свою очередь, через вызов функции Fakt, параметром которой также будет функция Fakt, и т. д., до тех пор, пока значение формального параметра N=1. Так как базовая часть описания рекурсивной функции Fakt определяет значение Fakt для N=1, равным единице, то рекурсивные вызовы функции Fakt больше не выполняются, а наоборот, выполняется вычисление функции Fakt для чисел, возрастающих от 1 до N, причем функция Fakt всякий раз возвращает значение, равное произведению очередного k-гo числа на факториал от k-1-го числа. Последнее возвращение результата вычисления функции Fakt присвоит переменной F значение произведения всех чисел от 1 до N, т. е. факториал числа N.
Вывод. При выполнении рекурсивной подпрограммы осуществляется многократный переход от некоторого текущего уровня организации алгоритма к нижнему уровню последовательно до тех пор, пока, наконец, не будет получено тривиальное решение поставленной задачи. В рассмотренном выше примере решение при N=1 тривиально, т.е. Fakt=l. Затем осуществляется возврат на верхний уровень с последовательным вычислением значения функции Fakt.
Следует учитывать, что использование рекурсивной формы организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека. Это объясняется тем, что при каждом входе в подпрограмму ее локальные переменные размещаются в особым образом организованной области памяти, называемой программным стеком.
Косвенная рекурсия
В Турбо Паскале есть случаи нетрадиционного объявления подпрограмм, когда в объявлении процедуры содержится директива 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; {Ханойские башни: перенести кольца с правого стержня на левый}
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);
Writeln;
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.
Задачи для индивидуального решения
.