Рекурсивные функции и процедуры

 

 

Если одна процедура (Pr_2) вызывает в своем разделе выполнения другую (Pr_1), то вызываемая процедура должна быть описана во внешней программе перед описанием вызывающей процедуры, либо внутри вызывающей процедуры. Возможны и циклические случаи: если процедура вызывает сама себя - прямая рекурсия, если обе процедуры вызывают в своих разделах выполнения друг друга - косвенная рекурсия.

 

 

 

Схема линейного взаимодействия процедур:

Pr_1 - раздел описания Pr_1 Pr_2 - раздел описания Pr_2

Pr_2 - раздел описания Pr_2 Pr_1 - раздел описания Pr_1

 

Вызов Pr_1 в процедуре Pr_2 Вызов Pr_1 в процедуре Pr_2

 

Внешняя программа Внешняя программа

 

Схема циклического взаимодействия процедур:

 

прямая рекурсия косвенная рекурсия

раздел описания программы Pr_2 - заголовок Pr_2 Forward;

Pr_1 - раздел описания Pr_1

Вызов Pr_2 в процедуре Pr_1

Pr_1 - раздел описания Pr_1

Pr_2 - раздел описания Pr_2

Вызов Pr_1 в процедуре Pr_1 Вызов Pr_1 в процедуре Pr_2

 

Внешняя программа Внешняя программа

 

 

Если процедура вызывает сама себя ( прямая рекурсия ), то она описывается как обычно. Рекурсия традиционно применяется для итерационного расчета значения функции с использованием результатов предыдущего шага. Например, для расчета выражений вида: X! ( X факториал ), X^N ( X в степени N ), вычисляемых по формулам: X_N= X_N-1 * k, где k - постоянная или переменная величина. В общем случае рекурсия применяется при расчете функции от функции: F_N(x) = F_N-1(x). При этом процесс происходит в два этапа: обратное движение с запоминанием цепочки расчета в оперативной памяти и прямое движение - расчет с использованием полученной цепочки. Рекурсивные процедуры требуют больше памяти для запоминания промежуточных результатов, чем обычные циклические операторы, поэтому рекурсии используются реже. В случае рекурсивных процедур следует обязательно предусмотреть условие окончания вызова процедуры.

Приведем пример традиционного использования рекурсии. Пусть требуется рассчитать число осколков, полученных в результате деления тела за " N" миллисекунд, если каждый осколок делится на два за одну миллисекунду. Тогда при N=0 число осколков = 1, при N> 0 число осколков = 2^N = 2*2^(N-1).

 

Функция, возвращающая число осколков, будет иметь вид:

 

Function K_O(N: word): Longint;

Begin

if N=0 then K_O: =1 {условие окончания рекурсии}

else K_O: =2*K_O(N-1) {рекурсивный вызов}

end;

 

 

Пример функции, возвращающей число осколков, без использования рекурсии:

 

Function K_O(N: word): Longint;

var N_1: Longint; i: word;

Begin

N_1: =1; for i: =1 to N do N_1: = 2*N_1; K_0: = N_1

end;

 

Если к каждому осколку добавляется два осколка, то число осколков = (1+2)^N= 3*3^(N-1).

 

Во внешней программе число осколков (переменная " NN" ) расчитывается вызовом функции:

 

NN: = K_O(t); где t - значение фактического параметра времени.

 

Практическое задание N 1. 31

Написать и отладить программы с использованием функций:

 

1. Рассчитать число зерен, выращенных крестьянином за " N" лет, если он посадил 10 зерен, а годовой урожай составляет 22 зерна на каждое посаженное зерно.

2. Рассчитать число рыбок - самок, выращенных в аквариуме за " N" месяцев, если вначале была одна самка, а ежемесячный прирост от одной самки составляет три самки, причем все рыбки остаются живые.

 

3. Рассчитать число золотых монет, принесенных в дань господину, если " N+1" подданных последовательно передают монеты от первого к последнему. Причем, первый отдает одну монету, второй увеличивает число монет вдвое, третий - в три раза и т. д.

4. Рассчитать число рыбок, выращенных в аквариуме за " N" лет, если вначале было две рыбки, а число рыбок увеличивается пропорционально числу лет, т. е. 4, 12, 48 и т. д.

 

5. Рассчитать функцию y=sin(sin(sin(... (sin(x))))), в которой имя функции " sin" повторяется N раз.

 

6. Рассчитать функцию y=a/(b+(a/(b+(a/(b+(... +a/b)))))), в которой знак деления " /" повторяется N раз.

 

Примечание: написать функцию для расчета с использованием прямой рекурсии и без рекурсивного вызова.

 

 

Если обе процедуры вызывают в своих разделах выполнения друг друга ( косвенная рекурсия ), то каждая из процедур должна быть описана ранее другой, что невозможно. В этом случае в разделе описания основной программы используется предварительное описание одной из процедур: пишется только заголовок процедуры и служебное слово Forward. Далее приводится полное описание второй процедуры, а затем полное описание первой процедуры (причем, второй раз в заголовке процедуры список формальных параметров можно не указывать).

Приведем пример использования рекурсии:

 

 

Program Rek; {раздел описания основной программы}

{---------------------------------------------------------------------}

Procedure pr_1(i: word); Forward; {предварительное описание процедуры pr_1}

{-----------------------------------------------------------------}

Procedure pr_2; {полное описание процедуры pr_2}

var ch: char; i: word;

Begin

Writeln('Купите десять билетов - выиграете миллион! ');

Writeln('Нажмите " Y" или " N" '); Readln(ch); i: =10;

if( ch='Y') or ( ch='y') then Pr_1(i) {вызов процедуры}

else Halt end;

{-----------------------------------------------------------------}

Procedure pr_1; {полное описание процедуры pr_1}

var n, n1: integer;

Begin

if i=10 then begin Randomize; n1: = Random(900)+100 end;

if (i = 0) then Pr_2 {условие окончания прямой рекурсии}

Else begin

repeat writeln('введите трехзначный номер билета');

Readln(n) until (n< 1000) and (n> 99);

if (n< > n1) then begin writeln('билет без выигрыша');

writeln('осталось ', i-1, 'билетов');

Pr_1(i-1) {прямая рекурсия} end

 

else begin Writeln('Вы угадали, получите выигрыш в банке! ');

Pr_2 {косвенная рекурсия} end end;

{-----------------------------------------------------------------}

BEGIN PR_2 {раздел выполнения основной программы} End.

 

Здесь процедура Pr_1 при первом вызове инициирует случайное трехзначное число " n1" - выигрышный номер. При каждом вызове процедура Pr_1 запрашивает ввод трехзначного номера билета " n". Если номер билета не совпал (n< > n1) и остались еще билеты (i< > 0), то снова вызывается процедура Pr_1, иначе вызывается процедура Pr_2 (окончание рекурсивного вызова). Если номера совпали (n1=n), то выводится сообщение: 'Вы угадали, получите выигрыш в банке! '. Процедура Pr_2 либо вызывает процедуру Pr_1, либо программа заканчивается (оператор Halt). В процедуре Pr_2 заголовок не имеет параметров, а в процедуре Pr_1 параметры указываются при первом описании. В данном случае приводится управляемая на каждом шаге рекурсия (процедура запрашивает номер билета). Включив тело процедуры Pr_2 в Pr_1 и введя операторы цикла, нетрудно избавиться от рекурсивного вызова процедур.

 

Практическое задание N 1. 32

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

Ученики двух групп имеют порядковые номера от 1 до N в каждой группе. В процедуре P_1 функцией Random определяются два числа " a" и " b" от 1 до N. Если числа разные, то два участника с номерами " a" и " b" выбывают, оставшиеся ученики перенумеровываются от 1 до (N-1) и играют дальше (процедура P_1 повторяется с новыми значениями " a" и " b" ), иначе выводится значение совпавшего номера, ученики получают приз и процедура P_2 предлагает играть снова.

 

 

Разработка модулей

 

 

Известно, что откомпилированная программа размещается в отдельном сегменте памяти, т. е. не может превышать 64 Кбайта. Для создания больших программ в Турбо-Паскале предусмотрено подключение к основной программе откомпилированных модулей. Модуль включает в себя, как правило, большое число процедур, выполняющих однотипные операции, например, работа с графикой, операции с комплексными числами, матричные операции и т. д. Модуль определяется как программа, начинающаяся со служебного слова " Unit" и включающая в себя интерфейсную, исполняемую и инициирующую части.

Интерфейсная часть модуля начинается со служебного слова " Interface" и состоит из раздела описания глобальных имен типов, меток, констант, переменных, а также заголовков процедур, доступных основной программе.

Исполняемая часть модуля начинается со служебного слова " Implementation" и содержит полное описание процедур (заголовок, разделы описания и выполнения), заголовки которых перечислены в интерфейсной части, а также локальных имен типов, меток, констант и переменных, используемых в инициирующей части.

Инициирующая часть модуля начинается со служебного слова " Begin" и содержит блок операторов, выполняемых при подключении модуля к основной программе. Инициирующая часть вместе со словом " Begin " может отсутствовать или быть пустой. Заканчивается модуль служебным словом " End. " с точкой.

Содержимое исполняемой и инициирующей частей не доступно основной программе, связь модуля с основной программой осуществляется через интерфейсную часть модуля.

Структура модуля имеет вид:

 

Unit Name_M; { Name_M - имя модуля }

{-----------------------------------------------------------------}

Interface { Интерфейсная часть модуля}

{------------------------------------ раздел описания глобальных имен}

Type MM= array[1..10, 1..10] of real; { описание типа}

Var Max_F, Min_F: real; {описание глобальных переменных}

{-----------------------------------------------------------------}

Procedure Name_P(p1: real; p2: MM); { описание заголовков процедуры}

Function Name_f(p3, p4: real): real; { и функции}

{-----------------------------------------------------------------}

Implementation {Исполняемая часть модуля}

{-------------------------------------- раздел описания локальных имен}

Const C = 'Подключен модуль Name_M'; { задание локальной константы}

Procedure Name_P; {Полное описание процедуры}

{ Раздел описания процедуры}

Begin { Раздел выполнения процедуры} End;

Function Name_f: real; {Полное описание функции}

{ Раздел описания функции}

Begin { Раздел выполнения функции} End;

{---------------------------------------------------------------- }

BEGIN { Инициирующая часть модуля}

Writeln(C); {операторы модуля}

END.

Отметим, что в интерфейсной части модуля запрещается делать опережающее описание процедур. Запрещается также рекурсия модулей.

 

Модуль записывается в файл с именем модуля, например, Name_M. pas. Затем файл компилируется, при этом получается файл с расширением ". tpu", например, Name_M. tpu, который автоматически записывается в каталог, указанный в опции Options, Directories, EXE & TPU, иначе - в текущий каталог. При запуске программы, использующей модуль, файл с расширением ". tpu" ищется в каталоге, указанном в опции Options, Directories, EXE & TPU или Unit Directories, либо в текущем каталоге.

 

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

 

Program Pr_1;

Uses Name_M1, Name_M2;

 

Если в основной программе имя идентификатора совпадает с именем, объявленным в интерфейсной части подключенного модуля, то используются значения, присвоенные идентификатору в программе. Если одинаковые имена встречаются в интерфейсной части подключенных модулей (например в Name_M1 и Name_M2), то используются значения, присвоенные идентификатору в последнем описанном модуле, т. е. в Name_M2.

 

Приведем пример разработки и подключения модуля. В модуле опишем процедуры работы с матрицами.

 

 

Unit MATR_1;

{-----------------------------------------------------------------}

Interface

{-----------------------------------------------------------------}

Type M = array[1..10, 1..10] of real;

M1 = array[1..10] of real;

Procedure MAT_1(a: M; var b: M; n: word);

Procedure MAT_2(a: M; var b: M1; n: word);

{-----------------------------------------------------------------}

Implementation

{-----------------------------------------------------------------}

Procedure MAT_1; {создание матрицы " B", транспонированной к " A" }

var i, j: word;

begin for i: =1 to N do for j: =1 to N do b[i, j]: =a[j, i]

end;

{-----------------------------------------------------------------}

Procedure MAT_2; {расчет квадратов диагональных элементов}

var i, j: word;

begin for i: =1 to N do b[i]: =a[i, i]*a[i, i]

end;

{-----------------------------------------------------------------}

END.

 

В основной программе PR_1 подключается модуль MATR_1 и используются процедуры MAT_1 и MAT_2.

 

Program PR_1;

Uses MATR_1;

Type MM = M; MM1 = M1;

Var a1, a2, a3: MM; b1, b2: MM1; i, j, n: word;

Begin Writeln('введите размерность матрицы N='); Readln(n);

Randomize;

for i: =1 to n do for j: =1 to n do a1[i, j]: =random(20)+1;

MAT_1(a1, a2, n); MAT_1(a2, a3, n);

MAT_2(a1, b1, n); MAT_2(a2, b2, n) end.

 

В результате двойного транспонирования исходной матрицы " a1" (из " a1" в " a2", из " a2" в " a3" ) получается матрица " a3" тождественная " a1" .

Матрицы " b1" и " b2" содержат квадраты диагональных элементов матриц " a1" и " a2". Типы массивов фактических параметров должны соответствовать типам массивов формальных параметров, описанных в модуле MATR_1. Можно использовать имена типов, заданные в интерфейсной части модуля или задавать новые имена типов.

 

Практическое задание N 1. 33

 

1. Написать и отладить программы с использованием модуля, содержащего процедуры расчета элементов линейных массивов " В", являющихся:

1_1. суммой элементов в столбцах матрицы " A" (NxM),

1_2. суммой элементов в строках матрицы " A" (NxM),

1_3. наибольшими элементами в строках матрицы " A" (NxM),

1_4. наименьшими элементами в строках матрицы " A" (NxM).

1_5. наибольшими элементами в столбцах матрицы " A" (NxM),

1_6. наименьшими элементами в столбцах матрицы " A" (NxM). N=30, M=10.

 

Значения элементов матрицы " A" определяются в основной программе функцией Random(10), N=15, M=6. Программа выводит на экран значения элементов массивов " A" и " В".

 

2. Составить модуль, содержащий процедуры или функции для расчета:

2_1. скалярного произведения двух векторов " A" и " B" длиной " N", т. е.

С= A * B = a₁*b₁ + a₂*b₂ +... + a_N*b_N, где N< =100.

2_2. суммирования двух матриц " A" и " B" размером (МxN), N< =30, M< =30, т. е.

С= A + B, где c₁₁= a₁₁+ b₁₁; b₁₂ = a₁₂+ b₁₂; и т. д. c_MN = a_MN+ b_MN.

2_3. умножения двух матриц " A" (МxN) и " B" (NxK), N< =30, K < =30, M< =30, т. е. С= A * B, где c_ij= a_i1* b_1j+ a_i2* b_2j +... + a_iN* b_Nj ; и т. д.

Элемент с индексом " i, j" новой матрицы " С" (МхК) получается как сумма произведений элементов i -ой строки матрицы " A" на соответствующие элементы j -ого столбца матрицы " В".

Значения элементов матрицы " A" определяются в основной программе функцией Random(200), М=5, N=10. Программа выводит на экран массивы " A", " В" и " С".

 

 

Модуль СRT

 

⇐ Предыдущая6789101112131415Следующая ⇒

Поделиться: