ЕГЭ-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-й способ — построение дерева вызовов:
- поскольку в начале каждого вызова на экран выводится значение единственного параметра функции, достаточно определить порядок рекурсивных вызовов и сложить значения параметров
- поскольку при выполняется два рекурсивных вызова, решать такую задачу «на бумажке» удобно в виде двоичного дерева (в узлах записаны значения параметров при вызове функции:
складывая все эти числа, получаем 25
Правильный ответ: 25.
2-й способ — подстановка:
можно обойтись и без дерева, учитывая, что при каждом вызове с n < 4 происходит два рекурсивных вызова; сумму чисел, полученных при вызове, обозначим через S(n):
Дан рекурсивный алгоритм. Найдите сумму чисел, которые.
Найдите сумму чисел, которые будут выведены при вызове F(1).
Решение:
Решение с помощью дерева:
Начинаем с единицы и строим дерево до тех пор, пока выполняется условие n < 6.
Складывая все эти числа, получаем 79
Решение без дерева:
Пусть S(n) – это сумма чисел, которые будут выведены при вызове F(n). Тогда
Выполняем вычисления:
S(1) = 1 + S(3) + S(3)
S(3) = 3 + S(5) + S(9) = 12 + S(5)
S(5)=5 + S(7) + S(15) = 5 + 7 + 15 = 27
Делаем обратный ход:
S(3) = 12 + 27 = 39
S(1) = 1 + 39 + 39 = 79
Дан рекурсивный алгоритм найдите сумму чисел которые будут выведены при вызове f 1
Чему равна сумма всех чисел, напечатанных на экране при выполнении вызова F(5)?
Первым действием процедура F(5) выведет число 5 и вызовет процедуры F(4) и F(2).
Далее процедура F(2) выведет на экран число 2 и вызовет процедуры F(1) и F(−1). Процедура F(1) выведет на экран число 1 и вызовет процедуры F(0) и F(−2). Функция F(0) выведет на экран число 0. Функции F(−1) и F(−2) выведут на экран числа −1 и −2.
Процедура F(4) выведет число 4 и вызовет процедуры F(3) и F(1). Процедура F(1) выведет на экран цифры 1, 0 и −2. Процедура F(3) выведет число 3 и вызовет процедуры F(2) и F(0). Процедура F(2) выведет на экран цифры 2, 1, −2, −1 и 0, а процедура F(0) выведет число 0.
В итоге на экране появятся числа 5, 4, 3, 2, 1, 0, −2, −1, 0, 1, 0, −2, 2, 1, 0, −2, −1.