Объяснение и разбор 23 задания егэ по информатике

На уроке рассмотрен разбор 23 задания ЕГЭ по информатике: дается подробное объяснение и решение заданий демоверсий и досрочных вариантов разных годов

К оглавлению

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

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

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

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

ФГБНУ "Федеральный институт педагогических измерений"

Содержание:

Объяснение темы «Динамическое программирование»
Решение 23 заданий ЕГЭ по информатике

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

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

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

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

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

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

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

Прибавить 1

Умножить на 2

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

✍ Решение:

Результат: 28

📹 Подробный разбор смотрите на видео:
📹 YouTube здесь📹 Видеорешение на RuTube здесь

23_2:

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

прибавь 1

умножь на 4

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

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

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

✍ Решение:

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

Возьмем такое наименьшее число, находящееся в интервале от 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 команд.

Результат: 10

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

📹 YouTube здесь

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

23_3: Демоверсия ЕГЭ 2018 информатика:

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

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

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

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

✍ Решение:

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

Поскольку 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

Результат: 60

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

📹 YouTube здесь

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

К оглавлению

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

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

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

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