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

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

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

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

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

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

КЭС:

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

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

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

Тип ответа:

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

Номер: 35359C

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

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

Ответ: 8421421

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

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

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

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

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

S(-3) = ε.
S(-2) = ε.
S(0) = ε.
S(1) = «1» ⧺ S(-3) ⧺ S(0) = «1».
S(2) = «2» ⧺ S(-2) ⧺ S(1) = «21».
S(4) = «4» ⧺ S(0) ⧺ S(2) = «421».
S(8) = «8» ⧺ S(4) ⧺ S(4) = «8421421».

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

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

Ответ: 8421421.

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

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

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

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