Question

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

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

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

Accepted Answer

7363543

Answer

Идея решения: проследить порядок выводов, раскрывая рекурсивные вызовы в глубину слева направо.

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

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

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

Порядок выводов: 7, 3, 6, 3, 5, 4, 3.

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