Рекурсивные алгоритмы
  главная : карта раздела : автора  
 


Интерактивный тренажер 11 демоверсии ЕГЭ 2017
"Рекурсивные алгоритмы"


Возникли вопросы, сомнения или появились замечания, пишите...


Разбор решения задания 11 демоверсии ЕГЭ 2016
Рекурсивные алгоритмы

Ниже записаны две рекурсивные процедуры, 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 - 3);

end;

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

 

Решение:

 

Паскаль, встретив команду  F(11), вызывает процедуру F и передает ей параметр n = 11:

 

в случае выполнения условия n > 0 выполняется следующая строка:  G(n - 1), вызывающая процедуру G после уменьшения n на 1

 

процедура G печатает звездочку и, в случае выполнения условия n > 1, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(7)

 

в случае выполнения условия n > 0 выполняется следующая строка:  G(n - 1), вызывающая процедуру G после уменьшения n на 1

 

процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(3)

 

в случае выполнения условия n > 0 выполняется следующая строка:  G(n - 1), вызывающая процедуру G после уменьшения n на 1

 

процедура G печатает звездочку и, в случае выполнения условия, уменьшает значение n на 3, затем с новым параметром вызывает процедуру F(-1)

 

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

 

А нам остается подсчитать, сколько раз печаталась звездочка. В нашем случае это произошло ровно 3 раз(а)

 

Итого, правильный ответ: 3

 

Внимание! Для прокрутки условия на анимации необходимо по нему произвести щелчок левой кнопкой мыши и нажать кнопку "ВНИЗ" или "ВВЕРХ"


Интерактивный тренажер 11 ЕГЭ ДЕМО 2015
на "Рекурсивные алгоритмы"

ПРИМЕЧАНИЕ:

Если уловие задания видно не полностью, щелкните по нему курсором мыши и нажмите клавишу «вниз» или «вверх»

Примеры заданий и их решений, генерируемых интерактивным тренажером по задачам11 ЕГЭ 2015
Рекурсивные алгоритмы.

 

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

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

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

Решение (способ 1, К.Ю. Поляков):

обозначим через S(n) сумму чисел, которая выводится при вызове F(n)
при n >= 5 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
S(n) = n при n >= 5
при n < 5 процедура выводит число n и дважды вызывает сама себя:
S(n) = n + S(n+1) + S(n+3)
при n < 5 в результате вызова F(1) получаем
S(1) = 1 + S(2) + S(4)
S(2) = 2 + S(3) + S(5) = 2 + S(3) + 5 = 7 + S(3)
S(3) = 3 + S(4) + S(6) = 3 + S(4) + 6 = 9 + S(4)
S(4) = 4 + S(5) + S(7) = 4 + 5 + 7 = 16
полученное значение S(4) = 16 подставляем в S(3) и «обратным ходом» доходим до F(1):
S(3) = 9 + 16 = 25
S(2) = 7 + 25 = 32
S(1) = 1 + 32 + 16 = 49
таким образом правильный ответ = 49

Решение (способ 2 - механический обратный ход)

S(n) = n при n >= 5
S(n) = n + S(n+1) + S(n+3)

Прокручиваем цикл сшагом -1 начиная от значения меньшего 5

S(4) = 4 + S(5) + S(7) = 4 + 5 + 7 = 16
S(3) = 3 + S(4)+S(6) = 3 + 16 + 6 = 25
S(2) = 2 + S(3) +S(5) = 2 + 25 + 5 = 32
S(1) = 1 + S(2) + S(4) = 1 + 32 + 16 = 49
таким образом правильный ответ = 49

Воспользуемся данным методом и попробуем решить следующую задачу, не тратя время на комментарии

Задача 2

Дан рекурсивный алгоритм:
procedure F(n: integer);
begin
writeln(n);
if n < 6 then begin
F(n+2);
F(n*3)
end
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).

Решение:

S(n) = n + S(n+2) + S(n*3) при n<6
S(n) = n при n>=6

Записываем прокрутку в общем виде

S(5) = 5 + S(7) + S(15)
S(4) = 4 + S(6) + S(12)
S(3) = 3 + S(5) + S(9)
S(2) = 2 + S(4) + S(6)
S(1) = 1 + S(3) + S(3)

из последнего уравнения видим, что нам нужны третье и пятое уравнение, поэтому окончательно получаем:

S(5) = 5 + S(7) + S(15) = 5+7+15 = 27
S(3) = 3 + S(5) + S(9) = 3 + 27 + 9 = 39
S(1) = 1 + S(3) + S(3) = 1 + 39 + 39 = 79

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

F(0) = 1,
F(1) = 1
F(n) = F(n–1) * F(n - 2), при n > 1
Чему равно значение функции F(14)?
В ответе запишите только натуральное число.

РЕШЕНИЕ:

F(0) = 1, F(1) = 1
1) используя заданную рекуррентную формулу, находим, что F(2) = F(2 - 1) * F(2 - 2) = 1
2) используя заданную рекуррентную формулу, находим, что F(3) = F(3 - 1) * F(3 - 2) = 1
3) используя заданную рекуррентную формулу, находим, что F(4) = F(4 - 1) * F(4 - 2) = 1
4) используя заданную рекуррентную формулу, находим, что F(5) = F(5 - 1) * F(5 - 2) = 1
5) используя заданную рекуррентную формулу, находим, что F(6) = F(6 - 1) * F(6 - 2) = 1
6) используя заданную рекуррентную формулу, находим, что F(7) = F(7 - 1) * F(7 - 2) = 1
7) используя заданную рекуррентную формулу, находим, что F(8) = F(8 - 1) * F(8 - 2) = 1
8) используя заданную рекуррентную формулу, находим, что F(9) = F(9 - 1) * F(9 - 2) = 1
9) используя заданную рекуррентную формулу, находим, что F(10) = F(10 - 1) * F(10 - 2) = 1
10) используя заданную рекуррентную формулу, находим, что F(11) = F(11 - 1) * F(11 - 2) = 1
11) используя заданную рекуррентную формулу, находим, что F(12) = F(12 - 1) * F(12 - 2) = 1
12) используя заданную рекуррентную формулу, находим, что F(13) = F(13 - 1) * F(13 - 2) = 1
13) используя заданную рекуррентную формулу, находим, что F(14) = F(14 - 1) * F(14 - 2) = 1

Ответ: 1

 

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

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

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

РЕШЕНИЕ:

F(4) = 4 + F(5) + F(7) = 16
F(3) = 3 + F(4) + F(6) = 25
F(2) = 2 + F(3) + F(5) = 32
правильный ответ = 32

 

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

F(0) = 1,
F(1) = 1
F(n) = F(n–1) * F(n - 2) + 5, при n > 1

Чему равно значение функции F(5)? В ответе запишите только натуральное число.

РЕШЕНИЕ:

1) используя заданную рекуррентную формулу, находим, что F(2) = F(2 - 1) * F(2 - 2) + 5 = 6
2) используя заданную рекуррентную формулу, находим, что F(3) = F(3 - 1) * F(3 - 2) + 5 = 11
3) используя заданную рекуррентную формулу, находим, что F(4) = F(4 - 1) * F(4 - 2) + 5 = 71
4) используя заданную рекуррентную формулу, находим, что F(5) = F(5 - 1) * F(5 - 2) + 5 = 786

Ответ: 786

 

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

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

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

РЕШЕНИЕ:

обозначим через S(n) сумму чисел, которая выводится при вызове F(n) при n >= 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
S(n) = n при n >= 6
при n < 6 процедура выводит число n и дважды вызывает сама себя:
S(n) = n + S(n+4) + S(n+5) + S(n*3) при n < 6
в результате вызова F(1) получаем:
S(5) = 5 + S(9) + S(10) + S(15) = 5 + 9 + 10 + 15 = 39
S(4) = 4 + S(8) + S(9) + S(12) = 4 + 8 + 9 + 12 = 33
S(3) = 3 + S(7) + S(8) + S(9) = 3 + 7 + 8 + 9 = 27
S(2) = 2 + S(6) + S(7) + S(6) = 2 + 6 + 7 + 6 = 21
S(1) = 1 + S(5) + S(6) + S(3) = 1 + 39 + 6 + 27 = 73

правильный ответ = 73

 

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

procedure F(n: integer);
begin
writeln('*');
if n > 0 then begin
writeln('*');
F(n-5);
F(n div 2);
F(n div 2);
end
end;

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

РЕШЕНИЕ:

S(N) = 1 при N <= 0
S(N) = 2 + S(N-2)+ S(N div 2) + S(N div 2) = 2 + S(N-2)+ 2*S(N div 2) при N>0

S(0) = 1
S(1) = 2 + S(1-2) + 2*S(1 div 2) = 2 + 1 + 2 = 5
S(2) = 2 + S(2-2) + 2*S(2 div 2) = 2 + 1 + 10 = 13
S(3) = 2 + S(3-2) + 2*S(3 div 2) = 2 + 1 + 10 = 13
S(4) = 2 + S(4-2) + 2*S(4 div 2) = 2 + 1 + 26 = 29
S(5) = 2 + S(5-2) + 2*S(5 div 2) = 2 + 1 + 26 = 29
S(6) = 2 + S(6-2) + 2*S(6 div 2) = 2 + 5 + 26 = 33
S(7) = 2 + S(7-2) + 2*S(7 div 2) = 2 + 13 + 26 = 41
S(8) = 2 + S(8-2) + 2*S(8 div 2) = 2 + 13 + 58 = 73

Таким образом правильный ответ = 73

 

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

procedure F(n: integer);
begin writeln('*');
if n > 0 then begin
writeln('*');
F(n-8);
F(n div 2);
end
end;

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

РЕШЕНИЕ:

S(N) = 1 при N <= 0
S(N) = 2 + S(N-2)+S(N div 2) при N>0

S(0) = 1
S(1) = 2 + S(1-2)+S(1 div 2) = 2 + 1 + 1 = 4
S(2) = 2 + S(2-2)+S(2 div 2) = 2 + 1 + 4 = 7
S(3) = 2 + S(3-2)+S(3 div 2) = 2 + 1 + 4 = 7
S(4) = 2 + S(4-2)+S(4 div 2) = 2 + 1 + 7 = 10
S(5) = 2 + S(5-2)+S(5 div 2) = 2 + 1 + 7 = 10
S(6) = 2 + S(6-2)+S(6 div 2) = 2 + 1 + 7 = 10

Таким образом правильный ответ = 10

 

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

F(0) = 1,
F(1) = 1
F(n) = F(n–1) * F(n - 2) + 5, при n > 1

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

РЕШЕНИЕ:

F(0) = 1,
F(1) = 1
F(2) = F(2 - 1) * F(2 - 2) + 5 = 6
F(3) = F(3 - 1) * F(3 - 2) + 5 = 11
F(4) = F(4 - 1) * F(4 - 2) + 5 = 71
F(5) = F(5 - 1) * F(5 - 2) + 5 = 786
F(6) = F(6 - 1) * F(6 - 2) + 5 = 55811
F(7) = F(7 - 1) * F(7 - 2) + 5 = 43867451

Ответ: 43867451

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

procedure F(n: integer);
F(1) = 1;
G(1) = 1;
F(n) = 8*F(n–1) – 8*G(n–1);
G(n) = F(n–1) + 3*G(n–1), при n >=2

Чему равно значение величины F(5) - G(5)? В ответе запишите только целое число.

РЕШЕНИЕ:

F(1) = 1 : G(1) = 1
F(2) = 8*F(1) - 8*G(1) = 0 : G(2) = F(1) + 3*G(1) = 4
F(3) = 8*F(2) - 8*G(2) = -32 : G(3) = F(2) + 3*G(2) = 12
F(4) = 8*F(3) - 8*G(3) = -352 : G(4) = F(3) + 3*G(3) = 4
F(5) = 8*F(4) - 8*G(4) = -2848 : G(5) = F(4) + 3*G(4) = -340
F[5] - G[5] = -2508

Таким образом правильный ответ = -2508


 

© Северобайкальск, Russia
Александр Козлов, 2017

  Рейтинг@Mail.ru