Задание 16. Рекурсивные алгоритмы
За правильное выполненное задание получишь 1 балл. На решение отводится примерно 9 минут.
Для выполнения задания 16 по информатике необходимо знать:
Рекурсия – это приём, позволяющий свести исходную задачу к одной или нескольким более простым задачам того же типа.
Чтобы определить рекурсию, нужно задать:
- условие остановки рекурсии (базовый случай или несколько базовых случаев)
- рекуррентную формулу
Любую рекурсивную процедуру можно запрограммировать с помощью цикла
Рекурсия позволяет заменить цикл и в некоторых сложных задачах делает решение более понятным, хотя часто менее эффективным
Задачи для тренировки
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
Бейсик | Python |
DECLARE SUB F(n) SUB F(n) IF n > 0 THEN PRINT n F(n - 3) F(n \ 3) END IF END SUB | def F(n): if n > 0: print(n) F(n - 3) F(n // 3) |
Паскаль | Алгоритмический язык |
procedure F(n: integer); begin if n > 0 then begin writeln(n); F(n - 3); F(n div 3) end end; | алг F(цел n) нач если n > 0 то вывод n, нс F(n - 3) F(div(n, 3)) все кон |
Си++ | |
void F(int n) { if (n > 0) { std: :cout << n F(n - 3); F(n / 3); } } |
Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Ниже на 2 языках программирования записан рекурсивный алгоритм F:
Паскаль | Си |
procedure F(n: integer); begin writeln('#'); if n <= 6 then begin F(n*2); F(n*2); F(n+2); end writeln('#'); end; | void F(int n) { std::cout <<"#"; if (n <= 6) { F(n*2); F(n*2); F(n+2); } std::cout <<"#"; } |
Сколько символов «решётка» будет напечатано на экране при выполнении вызова F(3)?
Ниже на 2 языках программирования записан рекурсивный алгоритм F:
Паскаль | С++ |
procedure F(n: integer); begin writeln(n); if n < 5 then begin F(n+3); F(n*2); F(n+1); end writeln(n); end; | void F(int n) if (n < 5) { |
Найдите сумму чисел, которые будут выведены при вызове F(1).
Ниже на 2 языках программирования записан рекурсивный алгоритм F:
Паскаль | С++ |
procedure F(n: integer); begin writeln(n); if n < 5 then begin F(n + 7); writeln(n); F(n + 3); end end; | void F(int n) { std::cout << n; if (n < 5) { F(n + 7); std::cout << n; F(n + 3); } } |
Найдите сумму чисел, которые будут выведены при вызове F(-1).
Ниже на 2 языках программирования записан рекурсивный алгоритм F:
Паскаль | С++ |
procedure F(n: integer); | void F(int n) |
Сколько символов «решётка» будет напечатано на экране при выполнении вызова F(10)?