Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.
Бейсик
|
1 2 3 4 5 6 7 8 9 10 11 |
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) IF n > 0 THEN G(n - 1) END SUB SUB G(n) PRINT "*" IF n > 1 THEN F(n - 3) END SUB |
Python
|
1 2 3 4 5 6 7 |
def F(n): if n > 0: G(n - 1) def G(n): print("*") if n > 1: F(n - 3) |
Алгоритмический язык
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
алг F(цел n) нач если n > 0 то G(n - 1) все кон алг G(цел n) нач вывод "*" если n > 1 то F(n - 3) все кон |
Паскаль
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
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; |
Си
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
void F(int n); void G(int n); void F(int n){ if (n > 0) G(n - 1); } void G(int n){ printf("*"); if (n > 1) F(n - 3); } |
Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(11)?
Ответ:
Демонстрационный вариант ЕГЭ 2016 г. – задание №11
Решение:
Рассмотрим задачу на языке Питон:
|
1 2 3 4 5 6 7 |
def F(n): if n > 0: G(n - 1) def G(n): print("*") if n > 1: F(n - 3) |
F(11) → G(10) → F(7) → G(6) → F(3) → G(2) → F(-1)
F(11) вызывает G(10), G(10) вызывает F(7) и тд. до вызова F(-1) (так как n = -1 не больше 0, следовательно действие программы прекращается).
При каждом вызове функции G(n) печатается *. Таким образом количество звездочек равно количеству вызовов функции G(). В данном случае функция G() вызывается 3 раза.
Ответ: 3