ЕГЭ по информатике 2020, часть 1, № 11 , рекурсия, результат работы алгоритма

ЕГЭ по информатике 2020, вариант Москва
Рекурсия, результат работы алгоритма
Часть 1, № 11
Задание взято с сайта
http://kotolis.ru/realegeinf_2020



Условие. Запишите подряд без пробелов и разделителей все числа, которые будут напечатаны на экране при выполнении вызова F(7). Числа должны быть записаны в том порядке, в котором они выводятся на экран.
Рекурсивный алгоритм F:
procedure F(n: integer);
begin
if F(n) >2 then begin
F(n div 2);
F(n–1);
write(n)
end;
end;

Сообщение отредактировано: swf - 19.07.20, 15:15

Решение.
Главная характеристика приведённого рекурсивного алгоритма –
наличие отложенного действия.
Прежде чем напечатать n, нужно дождаться, когда завершаться рекурсивные вызовы F(n div 2) и F(n–1).
В ситуации, когда в рекурсивном алгоритме (процедуре) есть отложенное действие, транслятор скрыто от пользователя образует стек и помещает туда все параметры текущего вызова, в данном случае n.
Стек можно представить как трубку с одним запаянным концом. Элементы вталкиваются и выталкиваются из стека через второй открытый конец:

Сообщение отредактировано: swf - 19.07.20, 15:16

При вызове F(7) в стек помещается n = 7:



Затем происходит рекурсивный вызов F(7 div 2) = F(3).

Добавлено 19.07.20, 15:07
Шаг 1. В вызове F(3) есть отложенное действие, поэтому параметр n = 3 тоже помещается в стек:



Шаг 2. Затем происходит рекурсивный вызов F(3 div 2) = F(1).
Так как 1 < 2, то этот вызов завершается без печати.
Шаг 3. Затем происходит рекурсивный вызов F(3 – 1) = F(2), который завершается без печати.
Шаг 4. Из стека выталкивается и печатается 3, вызов F(3) завершён, в стеке находится 7:



Печать: 3.

Затем происходит рекурсивный вызов F(7 – 1) = F(6).
Из-за отложенного действия (печати 6) 6 помещается в стек:



Затем происходит рекурсивный вызов F(6 div 2) = F(3) и повторяются шаги 1-4 (3 помещается в стек, затем удаляется из стека и печатается).
Печать: 33.

Затем происходит рекурсивный вызов F(6 – 1) = F(5), 5 помещается в стек:



Затем происходит рекурсивный вызов F(5 div 2) = F(2), который завершается без печати.
Затем происходит рекурсивный вызов F(5 – 1) = F(4), 4 помещается в стек:



Затем происходит рекурсивный вызов F(4 div 2) = F(2), который завершается без печати.

Затем происходит рекурсивный вызов F(4 – 1) = F(3), 3 помещается в стек:


Все оставшиеся новые вызовы завершаются без печати, затем из стека на печать выходят элементы 3, 4, 5, 6, 7.
Печать: 3334567.

Ответ: 3334567 .

Сообщение отредактировано: swf - 19.07.20, 15:17