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

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

Задание 22. Динамическое программирование: Демоверсия егэ по информатике 2020: объяснение и решение


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

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

Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя – это последовательность команд.

Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?

Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

✍ Решение:
 

  • Изобразим траекторию в виде луча, на котором отложим отрезки:

    • демо 2020

  • Поскольку 10 обязательно должна содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:
    • 1 * 2 
или
(1 -> 10) * (10 -> 20)
  • Найдем отдельно количество программ каждого из отрезков:
  • 1 -> 10 = 14
  • На интервале от 1 до 10 возьмем наименьшее число, для которого исполнима только одна из команд:
    • 6
6 + 1 = 7
6 * 2 = 12 - нельзя, вне интервала
  • Рассмотрим все числа интервала, двигаясь от большего к меньшему:

  • 10 -> 20 = 2
  • очевидно, что это две программы:

  • Выполним произведение полученных результатов:
    • 14 * 2 = 28

Результат: 28

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