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

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

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

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

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

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

КЭС:

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

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

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

Тип ответа:

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

Номер: 933635

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

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

Ответ: 1241248

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

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

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

Запись ⌊nd⌋ означает целую часть частного. Здесь деление выполняется при положительном n, поэтому дробная часть просто отбрасывается. Такой аргумент вычисляется до начала вложенного вызова.

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

S(-3) = ε.
S(-2) = ε.
S(0) = ε.
S(1) = S(-3) ⧺ S(0) ⧺ «1» = «1».
S(2) = S(-2) ⧺ S(1) ⧺ «2» = «12».
S(4) = S(0) ⧺ S(2) ⧺ «4» = «124».
S(8) = S(4) ⧺ S(4) ⧺ «8» = «1241248».

Порядок фактической печати при обходе вызовов:
1 → 2 → 4 → 1 → 2 → 4 → 8.
Убираем разделители и получаем 1241248.

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

Ответ: 1241248.

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

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

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

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