Question

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

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

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

Accepted Answer

9631231

Answer

Идея решения: проследить дерево рекурсии функции F(9), выписав все выводы в порядке их появления.

Функция F(n) выводит n, если n > 0, затем рекурсивно вызывает F(n − 3) и F(n // 3).

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

1. F(9): выводит 9, затем вызывает F(6) и F(3)
2. F(6): выводит 6, затем вызывает F(3) и F(2)
3. F(3): выводит 3, затем вызывает F(0) и F(1)
4. F(0): условие не выполнено, возврат
5. F(1): выводит 1, затем вызывает F(−2) и F(0)
6. F(−2): условие не выполнено, возврат
7. F(0): условие не выполнено, возврат
8. F(2): выводит 2, затем вызывает F(−1) и F(0)
9. F(−1): условие не выполнено, возврат
10. F(0): условие не выполнено, возврат
11. F(3): выводит 3, затем вызывает F(0) и F(1)
12. F(0): условие не выполнено, возврат
13. F(1): выводит 1, затем вызывает F(−2) и F(0)
14. F(−2): условие не выполнено, возврат
15. F(0): условие не выполнено, возврат

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

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