Основы алгоритмизации и программирования. Часть третья. Структурированные типы данных. Асламова В.С - 13 стр.

UptoLike

ВУЗ: 

АГТА | Ангарск

Составители: 

Рубрика: 

25
подобных. Возможен импорт объектных кодов, полученных в Турбо С и
других языках, но на практике он труднореализуем.
В Турбо Паскале возможно также накопление наиболее нужных и
удобных процедур. Чаще всего такую коллекцию называют библиотекой.
В Паскале, придерживаясь определённых правил, можно из
библиотеки брать определённую процедуру. Делается это с помощью
заголовка
“одалживаемой” из библиотеки процедуры, после которого
следует оператор EXTERNAL.
Рекурсия
Слово “рекурсия” произошло от термина recurrence, что в переводе с
английского означает возвращение, повторение.
В качестве примера рассмотрим числа Фибоначчи:
1, 1, 2, 3, 5, 8, 13 , 21, 34,. . . . . . . . . . . . . .
Первые два числа = 1, чтобы определить каждый последующий член
ряда можно воспользоваться рекуррентной формулой:
F[n]:=F[n-1]+F[n-2] для n>2 (1)
В формуле (1) использованы две рекурсии: для того, чтобы найти
каждый новый член ряда, надо возвратится к
двум предыдущим членам.
Вспомним из комбинаторики: перестановками из n элементов
называются такие соединения (комбинации), из которых каждое содержит
все n элементов, и которые отличаются друг от друга лишь порядком
расположения элементов.
Число перестановок из n элементов равно:
Здесь мы также встречаемся с рекурсией: n!=n·(n-1)!
Для этого случая было бы удобно, чтобы процедура (или
функция)
вызывали саму себя. Турбо Паскаль предоставляет такую возможность.
Пример 7:
В качестве примера рекурсивного обращения используем функцию
для вычисления факториала.
var f,M:longint;
function fact (n:integer): longint;
begin
P
n
=n!=n·(n-1)·(n-2). . . . .1
(n-1)!
26
if n=0 then fact:=1
else fact:= fact(n-1)*n;
end;
begin
writeln(′ввод M′);
readln(M);
f:=fact(M);
writeln (′M= ′,f);
end.
При обращении к функции f:=fact(M), фактический параметр М
передаёт свою копию формальному параметру n.
Если М>0, то возникает рекурсивное обращение к функции fact со
значением параметра М-1, создаётся копия тела функции и для нового
параметра М-1 выделяется новая переменная, локальная по отношению к
копии тела функции. Эта переменная получает копию значения М-1. Затем
вновь происходит обращение к функции со значением М-2 и т.д. пока
значение параметра не станет равно 1.
Определение числа перестановок можно написать с помощью
итерации.
program k;
var i:integer; perest:longint;
function factor(n:integer):longint;
var i:integer; p:longint;
begin
p:=1
if n>1 then
for i:=2 to n do
p:=p*i; factor:=p;
end;
begin
writeln(′ввод n′);
readln(i);
perest:= factor(i);
writeln(′число перестановок= ′,perest);
end.
Пример 8:
Выдать на печать в обратном порядке цифры целого положительного
числа n.
Составим процедуру REVERSE. 
подобных. Возможен импорт объектных кодов, полученных в Турбо С и                            if n=0 then fact:=1
других языках, но на практике он труднореализуем.                                            else fact:= fact(n-1)*n;
      В Турбо Паскале возможно также накопление наиболее нужных и                        end;
                                                                                         begin
удобных процедур. Чаще всего такую коллекцию называют библиотекой.
                                                                                              writeln(′ввод M′);
      В Паскале, придерживаясь определённых правил, можно из                                  readln(M);
библиотеки брать определённую процедуру. Делается это с помощью                               f:=fact(M);
заголовка “одалживаемой” из библиотеки процедуры, после которого                              writeln (′M= ′,f);
следует оператор EXTERNAL.                                                               end.
                                                                                               При обращении к функции f:=fact(M), фактический параметр М
                                       Рекурсия                                       передаёт свою копию формальному параметру n.
                                                                                               Если М>0, то возникает рекурсивное обращение к функции fact со
      Слово “рекурсия” произошло от термина recurrence, что в переводе с              значением параметра М-1, создаётся копия тела функции и для нового
английского означает возвращение, повторение.                                         параметра М-1 выделяется новая переменная, локальная по отношению к
      В качестве примера рассмотрим числа Фибоначчи:                                  копии тела функции. Эта переменная получает копию значения М-1. Затем
                      1, 1, 2, 3, 5, 8, 13 , 21, 34,. . . . . . . . . . . . . .       вновь происходит обращение к функции со значением М-2 и т.д. пока
      Первые два числа = 1, чтобы определить каждый последующий член                  значение параметра не станет равно 1.
ряда можно воспользоваться рекуррентной формулой:                                            Определение числа перестановок можно написать с помощью
                             F[n]:=F[n-1]+F[n-2] для n>2                        (1)   итерации.
      В формуле (1) использованы две рекурсии: для того, чтобы найти                     program k;
каждый новый член ряда, надо возвратится к двум предыдущим членам.                       var i:integer; perest:longint;
      Вспомним из комбинаторики: перестановками из n элементов                           function factor(n:integer):longint;
называются такие соединения (комбинации), из которых каждое содержит                     var i:integer; p:longint;
                                                                                         begin
все n элементов, и которые отличаются друг от друга лишь порядком
                                                                                                 p:=1
расположения элементов.                                                                          if n>1 then
       Число перестановок из n элементов равно:                                                  for i:=2 to n do
                         Pn=n!=n·(n-1)·(n-2). . . . .1                                            p:=p*i; factor:=p;
                                                                                         end;
                                      (n-1)!                                             begin
        Здесь мы также встречаемся с рекурсией: n!=n·(n-1)!                                      writeln(′ввод n′);
                                                                                                 readln(i);
       Для этого случая было бы удобно, чтобы процедура (или функция)                            perest:= factor(i);
вызывали саму себя. Турбо Паскаль предоставляет такую возможность.                               writeln(′число перестановок= ′,perest);
                                                                                         end.
        Пример 7:
       В качестве примера рекурсивного обращения используем функцию                         Пример 8:
для вычисления факториала.
                                                                                            Выдать на печать в обратном порядке цифры целого положительного
   var f,M:longint;
   function fact (n:integer): longint;                                                числа n.
   begin                                                                                    Составим процедуру REVERSE.
                                         25                                                                             26

Страницы