A2BE00 — Рекурсия и рекуррентные зависимости: ответ и решение

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

Ниже на пяти языках программирования записаны две рекурсивные функции (процедуры): 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(9)?

СВОЙСТВА ЗАДАНИЯ

КЭС:

3.7 Рекурсия. Рекурсивные процедуры и функции. Использование стека для организации рекурсивных вызовов

3.16 Динамическое программирование как метод решения задач с сохранением промежуточных результатов. Задачи, решаемые с помощью динамического программирования: вычисление рекурсивных функций, подсчёт количества вариантов, задачи оптимизации

3.17 Понятие об объектно-ориентированном программировании. Объекты и классы. Свойства и методы объектов. Объектно-ориентированный анализ. Разработка программ на основе объектно-ориентированного подхода. Инкапсуляция, наследование, полиморфизм

Тип ответа:

Краткий ответ

Номер: A2BE00

Статус задания: НЕ РЕШЕНО Ответить

Решение задания EGEINFA2BE00

Ответ: 3

Начальный вызов: F(9). Нужно посчитать напечатанные звёздочки.

Рекурсивный вызов выполняется полностью, прежде чем программа продолжит следующую строку вызывающей процедуры. Поэтому порядок команд существенен. При завершении вызова возвращаемся к месту его вызова; уже напечатанные символы сохраняются. Одинаковые вызовы в разных местах выполняются каждый раз и не объединяются.

Процедура F: при n ≥ 1 последовательно выполняются вызов G(n − 2).

Процедура G: печать звёздочки выполняется независимо от проверки условия; при n ≥ 2 последовательно выполняются вызов F(n − 1).

Обозначим через C_F(n) и C_G(n) количество звёздочек за один полный вызов. Тогда C_F(n) = 0 при n ≤ 0 и C_F(n) = C_G(n − 2) при n ≥ 1. Вторая процедура печатает одну звёздочку всегда: C_G(n) = 1 при n ≤ 1 и C_G(n) = 1 + C_F(n − 1) при n ≥ 2. Печать выполняется до проверки в G, поэтому последнее посещение G также надо учесть.

Полная цепочка вызовов:
1. F(9).
2. G(7) — печатается *.
3. F(6).
4. G(4) — печатается *.
5. F(3).
6. G(1) — печатается *.

В цепочке 3 вызовов G; каждый печатает ровно одну звёздочку. Вызовы F ничего не печатают. Получаем ***, число символов равно 3.

Проверка. Отдельное исполнение команд с явным стеком вызовов дало тот же счётчик 3. В трассировке учтены все 6 вызовов и 3 операций печати; после каждого завершения выполнение возвращается к следующей команде, а после ложного условия пропускается только его тело.

Ответ: 3.

Задание EGEINFA2BE00: Рекурсия и рекуррентные зависимости

Решение задания EGEINFA2BE00

Помочь улучшить сайт

Комментарии к решению