Информатика ЕГЭ 22 задание разбор

22-е задание: «Динамическое программирование»
Уровень сложности — повышенный,
Максимальный балл — 1,
Примерное время выполнения — 7 минут.

Разбор досрочного ЕГЭ по информатике 2019:

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

  1. Прибавить 1
  2. Умножить на 2

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

Ответ: 28

Показать решение:

📹 Видео


Разбор 22 задания ЕГЭ по информатике 2017 года ФИПИ вариант 10 (Крылов С.С., Чуркина Т.Е.):

Исполнитель Счетчик преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:

  1. Прибавь 5
  2. Умножь на 5

Первая команда увеличивает число на экране на 5, вторая умножает его на 5.
Программа для исполнителя Счетчик — это последовательность команд.

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

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 4 траектория будет состоять из чисел 9, 45, 50.

Ответ: 8

Показать решение:

  • Так как общая траектория 5 -> 250 содержит в себе и те отрезки, которые должны быть удалены (содержащие 105), то разобьем ее на несколько отрезков, отображенных на луче:
  • решение 22 задания егэ

    1. 5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
    2. 35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
    3. 35 -> 105 — «ненужная» часть траектории;
    4. 105 -> 250 — тоже «ненужная» часть.
  • Чтобы вычислить результат, т.е. количество программ, необходимо:
  • траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
    
    полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий
    
  • Перед тем, как рассчитывать каждый отрезок, условимся брать только числа кратные 5, так как на траектории получения числа 250 из числа 5 командами умножить на 5 или прибавить 5 будут встречаться только числа кратные 5! (5+5=10, 5*5 = 25; 10+5 = 15, 10*5=50 и т.п.).
  • Кроме того, будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел к наименьшим.
  • Расчет отрезка 1: 5 -> 35
    • Возьмем такое число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
    • 5 не подходит: применимы две команды в интервале до 35: 
      5 + 5 = 10 и 5 * 5 = 25
      10 подходит: применима только одна команда:
      10 + 5 = 15, а 10 * 5 = 50 - больше 35
      
    • Отобразим число 10 на графе, указав и саму команду и результат. Красным цветом обозначим количество команд для получения конкретного числа, а в круг будем обводить итоговое суммарное количество команд. То есть из 10 мы можем получить число 15, используя одну команду (10 + 5 = 15):
    • решение 22 задание на графах

    • Далее рассмотрим следующее, меньшее десяти число: это 5. Для него можно использовать 2 команды (5+5=10 и 5*5=25):
    • 1_1

    • Итого получили две программы.
    • Результат: 2


  • Расчет отрезка 2: 35 -> 250
  • Возьмем такое число, кратное 5, и, находящееся в интервале от 35 до 250, для которого применима только одна команда:
  • 55 
    т.к. 55 * 5 = 275 - это больше числа 250
    
  • Затем будем последовательно брать подходящие меньшие числа
  • 1_11

    Пояснение: поскольку это задача динамического программирования, то полученные в начале результаты, используются для дальнейших вычислений:

  • для числа 45 мы взяли результат, полученный для числа 50 (2);
  • для числа 40 мы взяли результат, полученный для числа 45 (3);
  • для числа 35 мы взяли результат, полученный для числа 40 (4);
  • Результат: 5

  • Расчет отрезка 3: 35 -> 105
  • Возьмем такое число кратное 5 и находящееся в интервале от 35 до 105, для которого применима только одна команда:
  • 35 
    т.к. 35 * 5 = 175 - больше числа 105
    

    2

    Результат: 1

  • Расчет траектории 4: 105 -> 250
  • 1
    Результат: 1

  • Посчитаем результат, согласно полученной формуле:
  • траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
    2 * (5 - 1 * 1) = 8
    

Разбор 22 задания ЕГЭ по информатике 2017 года ФИПИ вариант 15 (Крылов С.С., Чуркина Т.Е.):

У исполнителя Увеличитель две команды, которым присвоены номера:

  1. прибавь 1
  2. умножь на 4

Первая из них увеличивает число на экране на 1, вторая умножает его на 4.

Программа для Увеличителя – это последовательность команд.

Сколько есть программ, которые число 3 преобразуют в число 44?

Ответ: 10

Показать решение:

Использование графов

  • Возьмем такое число, находящееся в интервале от 3 до 44, для которого применима только одна команда:
  • 12 
    к нему применима только команда - прибавь 1 
    12 * 4 = 48 - это больше, чем 44 
    
  • Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):
  • 1
    Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

  • Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.
  • разбор 33 задания егэ
    Пояснение: поскольку это задача динамического программирования, то полученные промежуточные результаты, используются для дальнейших вычислений:

    • для 11 взят результат, полученный для 12 (1);
    • для 10 взят результат, полученный для числа 11 (2);
    • для 9 взят результат, полученный для 10 (3);
    • и т.д.
  • Для последнего числа 3 получено 10 команд.

📹 Видео


22 задание. Демоверсия ЕГЭ 2018 информатика:

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

Первая из них увеличивает число на экране на 1, вторая увеличивает его на 2, третья умножает на 3. Программа для исполнителя М17 – это последовательность команд.

Сколько существует таких программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений программы содержит числа 8 и 10? Траектория должна содержать оба указанных числа.

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

Ответ: 60

Показать решение:

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

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

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

  • 10 -> 12 = 2
  • 1

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

📹 Видео


Поделитесь уроком с коллегами и друзьями:

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

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

*
*

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