Рекурсивный подсчёт звёздочек

ЕГЭ · Информатика · Задание 16 · Основы программирования

ПовышеннаяФИПИ2778CCКороткий ответ≈ 4 минутыОтвет сверен с ключом

Ниже приведены две рекурсивные функции F и G. Функция F(n) вызывает G(n - 2), если n > 0. Функция G(n) печатает символ «*» и вызывает F(n - 1), если n > 1. Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(12)?

Python

1def F(n):
2    if n > 0:
3        G(n - 2)
4
5def G(n):
6    print("*")
7    if n > 1:
8        F(n - 1)

Условие как в банке ФИПИ — открыть и сверить

Впишите правильный ответ.

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): F и G.

Бейсик	Python
DECLARE SUB F(n) DECLARE SUB G(n) SUB F(n) IF n > 0 THEN G(n - 2) END SUB SUB G(n) PRINT "*" IF n > 1 THEN F(n - 1) END SUB	def F(n): if n > 0: G(n - 2) def G(n): print("*") if n > 1: F(n - 1)
Алгоритмический язык	Паскаль
алг F(цел n) нач если n > 0 то G(n - 2) все кон алг G(цел n) нач вывод "*" если n > 1 то F(n - 1) все кон	procedure F(n: integer); forward; procedure G(n: integer); forward; procedure F(n: integer); begin if n > 0 then G(n - 2); end; procedure G(n: integer); begin writeln('*'); if n > 1 then F(n - 1); end;
Си
void F(int n); void G(int n); void F(int n){ if (n > 0) G(n - 2); } void G(int n){ printf("*"); if (n > 1) F(n - 1); }

Сколько символов «звёздочка» будет напечатано на экране при выполнении вызова F(12)?

Ваш ответ

Формат: число или слово без единиц измерения; дробную часть отделяйте запятой.

3 уровня: от лёгкого толчка до почти готового решения. Следующий открывается, когда прочитан предыдущий, — чтобы не перепрыгнуть сразу к ответу.

1Мягкая — с чего смотретьуровень 1 из 3

Проследите цепочку рекурсивных вызовов, начиная с $F(12)$. В каком случае функция $G$ печатает звёздочку?

2Наводящая — какие числа считатьуровень 2 из 3

Каждый вызов $F(n)$ при $n > 0$ вызывает $G(n - 2)$, а каждый вызов $G(n)$ печатает одну звёздочку и при $n > 1$ вызывает $F(n - 1)$.

3Прямая — фактически решениеуровень 3 из 3

Цепочка имеет вид $F(12) \to G(10) \to F(9) \to G(7) \to F(6) \to G(4) \to F(3) \to G(1)$. Функция $G$ вызывается 4 раза.

Всё равно не складывается?Полное решение с обоснованием каждого шага — на отдельной странице.

Открыть решение

ПредыдущаяВывод рекурсивной функцииСледующаяПорядок рекурсивных вызовов

Задание 16 ЕГЭ, информатика