Трассировка рекурсивной функции

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

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

Ниже на пяти языках программирования записан рекурсивный алгоритм $F$. Во всех вариантах алгоритм выводит значение параметра $n$, а затем, если $n \ge 4$, вызывает функцию для $n - 1$ и для целой части от деления $n$ на 2. Запишите подряд без пробелов и разделителей все числа, которые будут выведены на экран при выполнении вызова $F(6)$. Числа должны быть записаны в том же порядке, в котором они выводятся на экран.

Python

1def F(n):
2    print(n, end='')
3    if n >= 4:
4        F(n - 1)
5        F(n // 2)

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

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

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

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

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

Ваш ответ

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

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

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

В каком порядке выполняются команды: сначала вывод текущего $n$, затем рекурсивный вызов для $n-1$, затем вызов для целой части от деления $n$ на 2?

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

Постройте дерево рекурсивных вызовов, начиная с $F(6)$, и записывайте число сразу при входе в функцию.

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

Последовательность вывода при обходе вызовов: $6 \to 5 \to 4 \to 3 \to 2 \to 2 \to 3$.

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

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

ПредыдущаяПодсчёт рекурсивных вызововСледующаяРекурсивная функция F

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