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

Дата изменения: 22 августа 2019
Задание 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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

*
*


Вставить формулу как
Блок
Строка
Дополнительные настройки
Цвет формулы
Цвет текста
#333333
Используйте LaTeX для набора формулы
Предпросмотр
\({}\)
Формула не набрана
Вставить