Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[19]

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

прямая рекурсия раздел описания программы

Pr 1 - раздел описания Pr 1 Вызов Pr 1 в процедуре Pr 1

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

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

Pr 2 - заголовок Pr 2 Forward;

Pr 1 - раздел описания Pr 1 Вызов Pr 2 в процедуре Pr 1

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

Вызов Pr 1 в процедуре Pr 2

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

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

Приведем пример традиционного использования рекурсии. Пусть требуется рассчитать число осколков, полученных в результате деления тела за "N" миллисекунд, если каждый осколок делится на два за одну миллисекунду. Тогда при N=0 число осколков = 1, при N>0 число осколков = 2N = 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){рекурсивный вызов}

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

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

Если к каждому осколку добавляется два осколка, то число осколков = (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 Haltend;

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

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

var n, n1: integer;

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(Bu угадали, получите выигрыш в банке!);

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 предлагает играть снова.

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

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



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53]