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

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

Ниже на пяти языках программирования записан рекурсивный алгоритм F.

Бейсик	Python
SUB F(n) PRINT n, IF n >= 7 THEN F(n - 1) F(n - 3) END IF END SUB	def F(n): print(n, end='') if n >= 7: F(n - 1) F(n - 3)
Алгоритмический язык	Паскаль
алг F(цел n) нач вывод n если n >= 7 то F(n - 1) F(n - 3) все кон	procedure F(n: integer); begin write(n); if n >= 7 then begin F(n - 1); F(n - 3) end end;
С++
void F(int n) { std::cout << n; if (n >= 7) { F(n - 1); F(n - 3); } }

Запишите подряд без пробелов и разделителей все числа, которые будут выведены на экран при выполнении вызова F(9). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

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

КЭС:

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

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

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

Тип ответа:

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

Номер: 3989D3

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

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

Ответ: 9876456

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

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

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

Обозначим S(n) — строку вывода полного вызова F(n), а ε — пустую строку. Результаты вложенных вызовов соединяются в порядке команд. Ниже отдельно записан результат каждого встречающегося аргумента; знак ⧺ означает соединение строк, а не сложение чисел. Это позволяет раскрыть рекурсию от самых коротких вызовов к исходному.

S(4) = «4» = «4».
S(5) = «5» = «5».
S(6) = «6» = «6».
S(7) = «7» ⧺ S(6) ⧺ S(4) = «764».
S(8) = «8» ⧺ S(7) ⧺ S(5) = «87645».
S(9) = «9» ⧺ S(8) ⧺ S(6) = «9876456».

Порядок фактической печати при обходе вызовов:
9 → 8 → 7 → 6 → 4 → 5 → 6.
Убираем разделители и получаем 9876456.

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

Ответ: 9876456.

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

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

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

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