Погода
Календарь
Май 2019
Пн Вт Ср Чт Пт Сб Вс
« Сен    
 12345
6789101112
13141516171819
20212223242526
2728293031  
Страницы сайта

Рекурсивные алгоритмы.

РЕКУРСИВНЫЕ ПРОЦЕДУРЫ И ФУНКЦИИ

  • Процедура (функция)– это вспомогательный алгоритм (фрагмент кода программы), который служит для выполнения определенных действий.
  • выполнения одинаковых действий в различных местах одной и той же программы;
  • разбивки программы (или другой процедуры или функции) на подзадачи для улучшения читаемости кода;
  • подпрограммы располагаются всегда выше основной программы:
  • сначала составляется заголовок процедуры или функции, в котором перечисляются формальные параметры, они обозначаются идентификаторами, как переменные (т.к. формальные параметры могут меняться, также как переменные):
var x,y:integer;
{ заголовок процедуры с формальными переменными x и y:}
procedure Sum(x,y:integer);
begin

end;
// основная программа
begin

end.

var x,y:integer;
{ заголовок функции с формальными переменными x и y:}
function Sum(x,y:integer):
integer;
begin

end;
// основная программа
begin

end.
  • в месте вызова процедуры в круглых скобках указываются фактические параметры (числовые значения либо арифметические выражения) в том же порядке:
  • функция вызывается немного иначе:
{ заголовок процедуры с формальными переменными x и y:}
procedure Sum(x,y:integer);
begin

end;
// основная программа
begin Sum(100,200)
end.
{ заголовок функции с формальными переменными x и y:}
function Sum(x,y:integer): integer;
begin

end;
// основная программа
begin
write (Sum(100,200))
end.
  • компилятор не будет выполнять процедуру (функцию) до момента ее вызова в основной программе;
  • пример работы процедуры и функции для сложения двух значений (порядок действий компилятора указан числами):
var x,y:integer;
procedure Sum(x,y:integer);
begin
//3. Выводим сумму двух запрошенных чисел
write(x+y);
end;
begin
// 1. запрашиваем два числа
readln(x,y);
// 2. передаем запрошенные числа в процедуру Sum(x,y)
end.
var x,y:integer;
function Sum(x,y:integer): integer;
begin
{3. Суммируем два числа и присваиваем значение функции:}
Sum:=x+y;
end;
begin
// 1. запрашиваем два числа
readln(x,y);
{2. передаем запрошенные числа в функцию и выводим результат:} write (Sum(x,y))
end.
  • Рекурсивной называется процедура, вызывающая сама себя:
procedure row(n:integer); 
begin
  if n >=1 then begin
write (n, ' ');
row(n-1)
  end;
end;
begin
row(10);
end.

Для использования рекурсии, необходимо задать:

  • условие остановки рекурсии (обычно, в виде условного оператора):
   if n >=1 then begin
  • рекуррентную формулу (обычно, вызов самой себя с измененным параметром):
row(n-1)

Решение заданий:

Задание 1. Чему равна сумма напечатанных на экране чисел при выполнении вызова F(9)?

procedure F(n: integer);
begin
  if n > 1 then begin
writeln(n);
  F(n — 2);
  F(n – 4)
end
end;

Задание 2. Ниже записаны две рекурсивные процедуры: F и G:
procedure F(n: integer); forward;
procedure G(n: integer); forward;
procedure F(n: integer);
begin
if n > 0 then
G(n — 1);
end;
procedure G(n: integer);
begin
writeln(‘*’);
if n > 1 then
F(n — 2);
end;

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?

Решение:

  1. заметим, что каждая функция вызывает другую (это называется косвенная рекурсия), причем, только один раз
  2. вот цепочка вызовов:

F(11) => G(10) => F(8) => G(7) => F(5) => G(4) => F(2) => G(1)

  • за один вызов функции G выводится одна звёздочка, внутри функции F звездочки не выводятся, поэтому за 4 вызова G будет выведено 4 звездочки.  Ответ: 4.

Задание 3.  Дан рекурсивный алгоритм:

procedure F(n: integer);
begin
writeln(n);
if n < 5 then begin
F(n + 1);
F(n + 3)
end
end;

Найдите сумму чисел, которые будут выведены при вызове F(1).

Решение (вариант 1, построение дерева вызовов):

  1. поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров
  2. поскольку при n<5 выполняется два рекурсивных вызова, решать такую задачу удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):

Складывая все эти числа, получаем 49.  Ответ: 49.

Задание 4.  Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:

F(1) = 1

F(n) = F(n–1) * n, при n > 1

Чему равно значение функции F(5)?

В ответе запишите только целое число.

Решение:

  1. используя заданную рекуррентную формулу, находим, что

F(5) = F(4) * 5

  • применив формулу еще несколько раз, получаем

F(5) = F(3) * 4 * 5 = F(2) * 3 * 4 * 5 = F(1) * 2 * 3 * 4 * 5

  • мы дошли до базового случая, который останавливает рекурсию, так как определяет значение F(1) = 1
  • окончательно F(5) = 1 * 2 * 3 * 4 * 5 = 120

Ответ: 120.

Задание 5.  Ал­го­ритм вы­чис­ле­ния зна­че­ния функ­ции F(n), где n – на­ту­раль­ное число, задан сле­ду­ю­щи­ми со­от­но­ше­ни­я­ми:

F(1) = 1

F(2) = 1

F(n) = F(n–1) * n − 2 * F(n–2), при n >2

Чему равно зна­че­ние функ­ции F(6)?

В от­ве­те за­пи­ши­те толь­ко на­ту­раль­ное число.

Решение:

По­сле­до­ва­тель­но на­хо­дим:

F(3) = F(2) * 3 − 2 * F(1) = 1,

F(4) = F(3) * 4 − 2 * F(2) = 2,

F(5) = F(4) * 5 − 2 * F(3) = 8,

F(6) = F(5) * 6 − 2 * F(4) = 44.

При­ме­ча­ние.

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

Ответ: 44

Задание 6.

Задание 7. (ЕГЭ по информатике демоверсия 2018 года).
Ниже на пяти языках программирования записан рекурсивный алгоритм F.

procedure F(n: integer); begin if n > 0 then begin write(n); F(n — 3); F(n div 3) end end;
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

  • Для удобства восприятия задания, выпишем рекуррентные формулы и условия остановки рекурсии для двух процедур:
Для F: 
* F(n - 2) при n > 10
G(n) при n <= 10
Для G:
**
F(n - 3) при n > 0
  • Выпишем последовательность вызовов процедур, начиная с указанного в задании F(18):
F(18) -> F(16) -> F(14) -> F(12) -> F(10) -> G(10) -> 
F(7) -> G(7) -> F(4) -> G(4) -> F(1) -> G(1) -> F(-2) -> G(-2)
  • Обратим внимание, что независимо от условия процедура F выводит на экран одну *, а процедура G выводит две *. Посчитаем для последовательности вызовов итоговую сумму звездочек: 9F + 5G = 9*1 + 5*2 = 19

  • Ответ: 19

Способ 2. Рассмотрим пошагово выполнение программы при вызове F(18):

1 шаг: F(18)        
* F(16)
2 шаг: * F(14)
3 шаг: * F(12)
4 шаг: * F(10)
5 шаг: * G(10)
6 шаг: ** F(7)
7 шаг: * G(7)
8 шаг: ** F(4)
9 шаг: * G(4)
10 шаг: ** F(1)
11 шаг: * G(1)
12 шаг: ** F(-2)
13 шаг: * G(-2)
14 шаг: **

Посчитаем количество звездочек: 19
Ответ: 19

Задание 8. (Демоверсия ЕГЭ по информатике 2019).
Ниже записан рекурсивный алгоритм F.
procedure F(n: integer); begin if n > 0 then begin F(n — 1); write(n); F(n — 2) end end;
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(4). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Результат: 1231412

Top