Question

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

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

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

Accepted Answer

5242312

Answer

Идея решения: проследить порядок вывода, разворачивая рекурсивные вызовы согласно условию $n \geq 3$.

Функция выводит текущее значение $n$, затем (если $n \geq 3$) рекурсивно вызывает себя с аргументами $n \div 2$ и $n - 1$.

Проследим вызовы для F(5):

1. F(5): выводит 5, затем вызывает F(2) и F(4)
2. F(2): выводит 2, условие не выполнено (2 < 3), возврат
3. F(4): выводит 4, затем вызывает F(2) и F(3)
4. F(2): выводит 2, возврат
5. F(3): выводит 3, затем вызывает F(1) и F(2)
6. F(1): выводит 1, возврат
7. F(2): выводит 2, возврат

Последовательность выводов: 5, 2, 4, 2, 3, 1, 2.

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