На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Rust
  
> ЕГЭ по информатике 2020, часть 1, № 11, рекурсия, результат работы алгоритма
    ЕГЭ по информатике 2020, вариант Москва
    Рекурсия, результат работы алгоритма
    Часть 1, № 11
    Задание взято с сайта
    http://kotolis.ru/realegeinf_2020

    user posted image

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

      user posted image
      Сообщение отредактировано: swf -
        При вызове F(7) в стек помещается n = 7:

        user posted image

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

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

        user posted image

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

        user posted image

        Печать: 3.

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

        user posted image

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

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

        user posted image

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

        user posted image

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

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

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

        Ответ: 3334567 .
        Сообщение отредактировано: swf -
        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
        0 пользователей:


        Рейтинг@Mail.ru
        [ Script execution time: 0,0203 ]   [ 16 queries used ]   [ Generated: 1.08.21, 09:50 GMT ]