Демоверсия егэ по информатике 2020. Задание 11

Авторadmin / Опубликовано

Задание 11. Рекурсивные процедуры и функции: Демоверсия егэ по информатике 2020: объяснение и решение


*** КАНАЛ ЮТЬЮБ ***
 
ЕГЭ по информатике -> ЕГЭ 2020 -> ЕГЭ 2020
 

Разбор 11 задания. Демоверсия егэ по информатике 2020, ФИПИ:

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

1
2
3
4
5
6
7
8
9

procedure F(n: integer);
begin
write(n);
if n >= 3 then
  begin
    F(n div 2);
    F(n - 1)
  end
end;
Бейсик:

SUB F(n)
PRINT n,
 IF n >= 3 THEN
   F(n \ 2)
   F(n - 1)
 END IF
END SUB
 Python:

def F(n):
 print(n, end='')
 if n >= 3:
    F(n // 2)
    F(n - 1)
 С++:

void F(int n) {
 std::cout << n;
 if (n >= 3) {
    F(n / 2);
    F(n - 1);
 }
}

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

📹 Видеоразбор 11 задания ЕГЭ демоверсии 2020

✍ Решение:
 

    Рассмотрим алгоритм:

  • В данном фрагменте программы рекурсивная процедура вызывает саму себя дважды.
  • Благодаря условию, находящемуся в процедуре (if n >= 3 — условие остановки рекурсии), обеспечивается выход из рекурсии и не происходит «зацикливания».
  • Выполнение процедур закончится, когда в каждой из вызванных процедур выполнятся по две внутренние процедуры, и условие if n >= 3 перестанет работать (т.е. когда параметр процедуры n станет < 3).
  • div — целочисленное деление, т.е., например:
    • 5 div 2 = 2
1 div 2 = 0
  • Отобразим пошагово выполнение каждой процедуры, двигаясь сверху вниз; в каждой процедуре разместим именно те действия, которые происходят в данной процедуре. Будем выделять цифры, выводимые на экран:
    • F(5) = 5 F(2) F(4) = ?
F(4) = 4 F(2) F(3) = ?
F(3) = 3 F(1) F(2) = ?
F(2) = 2 
F(1) = 1
  • Теперь, будем двигаться снизу вверх, подставляя вместо вызовов процедур полученные значения:
    • F(1) = 1 
F(2) = 2 
F(3) = 3 F(1) F(2) = 312
F(4) = 4 F(2) F(3) = 42312
F(5) = 5 F(2) F(4) = 5242312
  • Получаем, что при вызове F(5) будут выведены цифры 5242312.

Результат: 5242312

К оглавлению
Далее