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

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

Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма

До ЕГЭ 2021 года — это было задание № 22 ЕГЭ

Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ

Задание 23_4:

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

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

Прибавить 1

Умножить на 2

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

Ответ: 28

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

📹 Видео

📹 Видеорешение на RuTube здесь

Задание 23_2:

23_2:

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

прибавь 1

умножь на 4

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

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

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

Ответ: 10

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

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

Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:

12 
к нему применима только команда - прибавь 1 
12 * 4 = 48 - это больше, чем 44

Отобразим число 12 на графе, указав и саму команду и результат. То есть для 12 можно использовать только одну команду (12 + 1 = 13):

Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.

Дальше будем использовать метод решения с конца, т.е. двигаясь от наибольших подходящих чисел (в конкретном случае с 12) — к наименьшим.

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

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

Для последнего числа 3 получено 10 команд.

📹 Видео (теоретическое решение)

📹 Видеорешение на RuTube здесь (теоретический способ)

Задание 23_3:

23_3. Демоверсия ЕГЭ 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
очевидно, что это две программы:

10 -> 12 = 2

Выполним произведение полученных результатов:

15 * 2 * 2 = 60

📹 Видео (теоретическое решение)

📹 Видеорешение на RuTube здесь