PROGRAM PG9_9;

VAR А, В: INTEGER;

FUNCTION BILL(Y, X: INTEGER): INTEGER;

VAR К: INTEGER;

BEGIN

К:=0;

WHILE Y MOD X <> 0 DO

BEGIN

К:= K+Y DIV X+2;

Y:= A-X+Y MOD X;

END;

BILL:= K+Y DIV X

END;

BEGIN

REPEAT

WRITE('BBEДИTE ДВА НАТУРАЛЬНЫХ ЧИСЛА А>В');

READLN(A, В);

UNTIL A> = B;

WRITELN('КОЛИЧЕCTBO ОТРЕЗКОВ В ТРАЕКТОРИИ:', BILL(A, В))

END.

Для решения задачи:

- формируем тело программы и описываем переменные;

- создаем описание функции BILL;

- вводим два натуральных числа А и В;

- вызываем функцию BILL для определения количества отрежов;

- завершаем работу программы.

Переменные:

в функции BILL:

X, Y - два натуральных числа (формальные параметры);

К - вспомогательная переменная (локальная переменная);

А - длинная сторона стола (глобальная переменная);

в основной программе:

А, В - два натуральных числа (глобальные переменные).

 

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

Формально рекурсию для функции F(X) можно описать сле­дующим образом:

IF X = <начальное значение> THEN

F:= <начальное значение функции>;

ELSE

F:= W(F);

где конструкция F:= <начальное значение функции>; называется глубиной рекурсии, a F:= W (F) определяет способ обращения функции в точке Хп к своим значениям для меньших значений аргумента Хп - 1, Хп - 2 и т. д.

Классическим примером простейшей рекурсии (линейной) может служить функция вычисления факториала натурального числа N FACT(N).

IF N = 0 THEN

FACT:= 1

ELSE

FACT:= N * FACT(N - 1);

Например, при N = 4 к функции FACT происходит обращение 5 раз (для N = 4, N = 3, N = 2, N = 1, N = 0), каждое из которых, кроме последнего, заносится в стек. При 5-м обращении вычисля­ется FACT(O) = 1, и затем последовательно, извлекая обращения из стека, вычисляются

FACT(1) = 1* FACT(O) = 1,

FACT(2) = 2*FACT(1) = 2,

FACT(3) = 3* FACT(2) = 6,

FACT(4) = 4*FACT(3) = 12.

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

Задача 9.10 Вычислить I-е число Фибоначчи.

Известно, что каждое последующее число Фибоначчи равняет­ся сумме двух предыдущих:

F _i:= F _i-1 + F _i-2;а нулевое число равно нулю, первое - единице.

Данная задача относится к каскадным рекурсиям, когда для вычисления одного значения требуется несколько вызовов для разных предыдущих значений.