Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 8 минут.
Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма
"Один из распространенных способов выполнения этого задания – выписать последовательность
рекуррентных формул, определяющих, сколькими способами можно получить текущее число из ближайших предшественников, одновременно производя вычисления по этим формулам. «Ближайших» в данном случае означает тех, из которых текущее число получается в результате применения программы, состоящей из одной команды. Когда текущее число сравняется с заданным, количество таких способов и будет искомым числом программ"
Типичные ошибки и рекомендации по их предотвращению:
"Не стоит пытаться перечислить все пути в явном виде, это слишком трудоёмко и, скорее всего, в итоге приведёт к ошибке. Распространённая ошибка – экзаменуемые в процессе рекуррентных вычислений забывают о том, что траектория обязана содержать или не содержать указанные в условии числа"
Объяснение темы «Динамическое программирование»
- Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
- Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
- «подсчитайте количество способов…»;
- «как оптимально распределить…»;
- «найдите оптимальный маршрут…».
- Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.
Более подробное знакомство с динамическим программированием доступно по ссылке.
Решение 23 заданий ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube: 
Задание демонстрационного варианта 2022 года ФИПИ
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
- Прибавить 1
- Умножить на 2
Сколько существует программ, для которых при исходном числе 3 результатом является число 37 и при этом траектория вычислений содержит число 18?
✍ Решение:
Результат: 28
📹 Подробный разбор смотрите на видео:
📹 YouTube здесь📹 Видеорешение на RuTube здесь
У исполнителя Увеличитель две команды, которым присвоены номера:
- прибавь 1
- умножь на 4
Первая из них увеличивает число на экране на 1, вторая умножает его на 4.
Программа для Увеличителя – это последовательность команд.
Сколько есть программ, которые число 3 преобразуют в число 44?
✍ Решение:
- Возьмем такое наименьшее число, находящееся в интервале от 3 до 44, для которого применима только одна команда:
12 к нему применима только команда - прибавь 1 12 * 4 = 48 - это больше, чем 44
Пояснение: Красным цветом будем выделять количество команд для получения конкретного числа, а в круг обводить итоговое суммарное количество команд.
Пояснение: поскольку это задача динамического программирования, то полученные промежуточные результаты, используются для дальнейших вычислений:
- для 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? Траектория должна содержать оба указанных числа.
✍ Решение:
- Изобразим траекторию в виде луча, на котором отложим отрезки:
- Поскольку 8 и 10 обязательно должны содержаться в расчете, то для поиска общего количества программ необходимо найти произведение количества программ отдельных отрезков:
1 * 2 * 3 или (2 -> 8) * (8 -> 10) * (10 -> 12)
2 -> 8 = 157 7 + 1 = 8 7 + 2 = 9 - нельзя, вне интервала
8 -> 10 = 2
10 -> 12 = 2
15 * 2 * 2 = 60
Результат: 60
📹 Подробное решение 23 (теоретическое) задания демоверсии ЕГЭ 2018 доступно на видео:
📹 Видеорешение на RuTube здесь
Галина
Вариант 15 опечатки:
9*4=36, а не 37.
5*4=20, а не 15.
admin
Спасибо! исправлено