Question

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

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

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

Accepted Answer

7251311

Answer

Идея решения: проследить порядок выводов при рекурсивном вызове, учитывая, что каждый вызов сначала печатает текущее значение, затем рекурсивно вызывает функцию с аргументами $n \div 3$ и $n - 2$.

Проанализируем вызов F(7):

1. F(7): выводит 7, затем вызывает F(2) и F(5).

2. F(2): выводит 2, затем вызывает F(0) и F(0). Оба условия $n > 0$ не выполнены, вывод прекращается.

3. F(5): выводит 5, затем вызывает F(1) и F(3).

4. F(1): выводит 1, затем вызывает F(0) и F(-1). Оба условия не выполнены.

5. F(3): выводит 3, затем вызывает F(1) и F(1).

6. F(1): выводит 1 (первый вызов из F(3)).

7. F(1): выводит 1 (второй вызов из F(3)).

Порядок выводов: 7 → 2 → 5 → 1 → 3 → 1 → 1.

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