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

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

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

"Один из распространенных способов выполнения этого задания – выписать последовательность рекуррентных формул, определяющих, сколькими способами можно получить текущее число из ближайших предшественников, одновременно производя вычисления по этим формулам. «Ближайших» в данном случае означает тех, из которых текущее число получается в результате применения программы, состоящей из одной команды. Когда текущее число сравняется с заданным, количество таких способов и будет искомым числом программ"

Типичные ошибки и рекомендации по их предотвращению:

"Не стоит пытаться перечислить все пути в явном виде, это слишком трудоёмко и, скорее всего, в итоге приведёт к ошибке. Распространённая ошибка – экзаменуемые в процессе рекуррентных вычислений забывают о том, что траектория обязана содержать или не содержать указанные в условии числа"

Объяснение темы «Динамическое программирование»

Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
«подсчитайте количество способов…»;
«как оптимально распределить…»;
«найдите оптимальный маршрут…».
Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.

Более подробное знакомство с динамическим программированием доступно по ссылке.

Решение 23 заданий ЕГЭ по информатике

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

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

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

✍ Решение:

Результат: 28

📹 Подробный разбор смотрите на видео:

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

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

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

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

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

✍ Решение:

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

5 -> 35 — обязательная часть, т.е. расчет количества программ по данной части траектории должен быть включен в результат;
35 -> 250 — отрезок, из которого нужно будет вычесть часть «ненужной» траектории («ненужная» траектория — которая включает число 105);
35 -> 105 — «ненужная» часть траектории;
105 -> 250 — тоже «ненужная» часть.

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

Результат: 5

Результат: 1

Результат: 8

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

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

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

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

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

✍ Решение:

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

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

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

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

Результат: 10

📹 Предлагаем посмотреть видео с решением данного 23 задания (теоретическое решение):

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

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

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

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

✍ Решение:

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

Результат: 60

📹 Подробное решение 23 (теоретическое) задания демоверсии ЕГЭ 2018 доступно на видео:

📎📎📎📎📎📎📎📎📎📎