Решение (вариант 2, динамическое программирование):
Базовый уровень, время – 5 мин)
Тема: рекурсивные алгоритмы.
Что нужно знать:
· рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа
· чтобы определить рекурсию, нужно задать
o условие остановки рекурсии (базовый случай или несколько базовых случаев)
o рекуррентную формулу
· любую рекурсивную процедуру можно запрограммировать с помощью цикла
· рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
· существуют языки программирования, в которых рекурсия используется как один из основных приемов обработки данных (Lisp, Haskell)
Пример задания:
Р-05. Ниже записаны две рекурсивные процедуры: 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)
3) за один вызов функции G выводится одна звёздочка, внутри функции F звездочки не выводятся, поэтому за 4 вызова G будет выведено 4 звездочки
4) Ответ: 4.
Ещё пример задания:
Р-05. Дан рекурсивный алгоритм:
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) поскольку при 
выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции):
3) складывая все эти числа, получаем 49
4) ответ: 49.
Решение (вариант 2, подстановка):
1) можно обойтись и без дерева, учитывая, что при каждом вызове с n < 5 происходит два рекурсивных вызова; сумму чисел, полученных при вызове 
, обозначим через 
:
2) выполняем вычисления:
3) теперь остаётся вычислить ответ «обратным ходом»:
4) 
5) Ответ: 49.
Ещё пример задания:
Р-04. Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln(n);
if n < 6 then begin
F(n+2);
F(n*3)
End
end;
Найдите сумму чисел, которые будут выведены при вызове F(1).
Решение (вариант 1, метод подстановки):
1) сначала определим рекуррентную формулу; обозначим через G(n) сумму чисел, которая выводится при вызове F(n)
|
|
|
2) при n >= 6 процедура выводит число n и заканчивает работу без рекурсивных вызовов:
G(n) = n при n >= 6
3) при n < 6 процедура выводит число n и дважды вызывает сама себя:
G(n) = n + G(n+2) + G(3n) при n < 6
4) в результате вызова F(1) получаем
G(1) = 1 + G(3) + G(3)
G(3) = 3 + G(5) + G(9) = 3 + G(5) + 9
G(5) = 5 + G(7) + G(15) = 5 + 7 + 15 = 27
5) используем обратную подстановку:
G(3) = 3 + G(5) + 9 = 3 + 27 + 9 = 39
G(1) = 1 + 2*G(3) = 79
6) Ответ: 79.
Решение (вариант 2, динамическое программирование):
1) п. 1-3 такие же, как в первом варианте решения
2) заполняем таблицу G(n) при n >= 6 (где G(n) = n)
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| G(n) | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
3) остальные ячейки заполняем, начиная с n = 5 справа налево, используя формулу :
G(n) = n + G(n+2) + G(3n)
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| G(n) | 79 | 30 | 39 | 22 | 27 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
4) ответ читаем в самой левой ячейке
5) Ответ: 79.
Пример задания:
Р-03. Дан рекурсивный алгоритм:
procedure F(n: integer);
Begin
writeln('*');
if n > 0 then begin
F(n-2);
F(n div 2)
End
end ;
Сколько символов "звездочка" будет напечатано на экране при выполнении вызова F(7)?
Дата добавления: 2019-02-22; просмотров: 868; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!