ЕГЭ-2015 задание 11.

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

Теория

  • рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа (существует прямая и обратная рекурсии)
  • чтобы определить рекурсию, нужно задать:
  • - рекуррентную формулу 
  • - условие остановки рекурсии (базовый случай или несколько базовых случаев)
  • любую рекурсивную процедуру можно запрограммировать с помощью цикла
  • рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным

Задача

Дан рекурсивный алгоритм F (для простоты приведен код на языке программирования Паскаль):

  • 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. поскольку при   выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции:

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

складывая все эти числа, получаем 25

Правильный ответ: 25.

2-й способ - подстановка:

можно обойтись и без дерева, учитывая, что при каждом вызове с n < 4 происходит два рекурсивных вызова; сумму чисел, полученных при вызове, обозначим через  S(n):

выполняем вычисления:

  • S(1) = 1 + S(2) + S(4) = S(2) + 5
  • S(2) = 2 + S(3) + S(5) = S(3) + 7
  • S(3) = 3 + S(4) + S(6) = 13
  • S(4) = 4

Правильный ответ: 25.

Яндекс.Метрика