Question

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

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

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

Accepted Answer

3120101

Answer

Идея решения: проследить порядок выводов при рекурсивном вызове, учитывая, что функция печатает текущее значение, а затем (при $n \geq 2$) вызывает себя трижды с аргументами $n-2$, $n-1$, $n-2$.

Проследим выполнение F(3):

1. F(3): выводит 3, затем вызывает F(1), F(2), F(1)
2. F(1): выводит 1 (условие $n \geq 2$ не выполнено, рекурсия прекращается)
3. F(2): выводит 2, затем вызывает F(0), F(1), F(0)
4. F(0): выводит 0 (условие не выполнено)
5. F(1): выводит 1
6. F(0): выводит 0
7. F(1): выводит 1 (последний вызов из F(3))

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

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