Уровень сложности — повышенный,
Требуется использование специализированного программного обеспечения — нет,
Максимальный балл — 1,
Примерное время выполнения — 8 минут.
Проверяемые элементы содержания: Умение анализировать результат исполнения алгоритма
"Один из распространенных способов выполнения этого задания – выписать последовательность
рекуррентных формул, определяющих, сколькими способами можно получить текущее число из ближайших предшественников, одновременно производя вычисления по этим формулам. «Ближайших» в данном случае означает тех, из которых текущее число получается в результате применения программы, состоящей из одной команды. Когда текущее число сравняется с заданным, количество таких способов и будет искомым числом программ"
Типичные ошибки и рекомендации по их предотвращению:
"Не стоит пытаться перечислить все пути в явном виде, это слишком трудоёмко и, скорее всего, в итоге приведёт к ошибке. Распространённая ошибка – экзаменуемые в процессе рекуррентных вычислений забывают о том, что траектория обязана содержать или не содержать указанные в условии числа"
Объяснение темы «Динамическое программирование»
- Динамическое программирование – это способ или техника решения сложных задач путем приведения их к более простым подзадачам того же типа.
- Динамическое программирование позволяет решать задачи, которые требуют полного перебора вариантов. Задание может звучать так:
- «подсчитайте количество способов…»;
- «как оптимально распределить…»;
- «найдите оптимальный маршрут…».
- Динамическое программирование позволяет увеличить скорость выполнения программы за счет эффективного использования памяти; полный перебор всех вариантов не требуется, поскольку запоминаются и используются решения всех подзадач с меньшими значениями параметров.
Более подробное знакомство с динамическим программированием доступно по ссылке.
Решение 23 заданий ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Исполнитель преобразует число на экране. У исполнителя есть две команды, которым присвоены номера:
- Прибавить 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
— тоже «ненужная» часть.- Чтобы вычислить результат, т.е. количество программ, необходимо:
траектория 1 * (траектория 2 - (траектория 3 * траектория 4)) полученные значения в каждом отрезке общей траектории необходимо перемножить, но при этом вычесть результат произведения значений "ненужных" траекторий
5 -> 35
- Возьмем такое наименьшее число, кратное 5 и, находящееся в интервале от 5 до 35, для которого применима только одна команда:
5 не подходит: применимы две команды в интервале до 35: 5 + 5 = 10 и 5 * 5 = 25 10 подходит: применима только одна команда: 10 + 5 = 15, а 10 * 5 = 50 - больше 35
Результат: 2
35 -> 250
55 т.к. 55 * 5 = 275 - это больше числа 250
Пояснение: поскольку это задача динамического программирования, то полученные в начале результаты, используются для дальнейших вычислений:
Результат: 5
35 -> 105
35 т.к. 35 * 5 = 175 - больше числа 105
Результат: 1
105 -> 250
траектория 1 * (траектория 2 - (траектория 3 * траектория 4))
2 * (5 - 1 * 1) = 8
Результат: 8
У исполнителя Увеличитель две команды, которым присвоены номера:
- прибавь 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 = 15
7 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
Спасибо! исправлено