ЕГЭ 2019 по информатике задание 22
Тема: «Динамическое программирование»
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 2
2. Умножить на 2
3. Прибавить 3
Первая из них увеличивает число на экране на 2, вторая умножает его на 2, третья увеличивает его на 3. Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 22 и при этом траектория вычислений программы содержит число 11?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 9, 18, 21.
Данный пример взят из демоверсии 2019 по информатике на сайте http://fipi.ru
РЕШЕНИЕ
Данная задача относится к динамическому программированию.
Динамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи.
Ключевая идея в динамическом программировании достаточно проста. Как правило, чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение
Для начала рассмотрим пример проще:
Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Сколько существует таких программ, которые преобразуют исходное число 2 в число 9 ?
Для решения построим таблицу:
Из таблицы видео, чтобы получить, например, число 5, необходимо выполнить одну команду +1, т.е 4+1 =5. При этом для самого числа 4 было найдено 2 программы. Разберём ещё один пример числа 8:
Таким образом в данном примере ответом будет 5 программ.
В задаче № 22 ЕГЭ 2019 по информатике написано дополнительное условие: траектория вычислений программы содержит число 11. Это означает, что число 11 должно обязательно войти в траекторию.
Построим таблицу сначала до числа 11, а затем до 22:
Проанализируем количество команд для числа 12:
Проанализируем количество команд для числа 13:
Проанализируем количество команд для числа 14:
По аналогии анализируем оставшееся числа. В последнем числе 22 будет найдено 100 программ.
Ответ: 100
[newsletter_signup_form id=1]
Самостоятельная работа
Исполнитель Вычислитель преобразует число, записанное на экране.
У исполнителя есть три команды, которым присвоены номера:
- Умножить на 3
- Прибавить 2
- Прибавить 3
Первая из них умножает число на экране на 3, вторая увеличивает его на 2, третья увеличивает его на 3.
Программа для Вычислителя – это последовательность команд.
Сколько существует таких программ, которые преобразуют исходное число 2 в число 21 и при этом траектория вычислений программы содержит число 15?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 123 при исходном числе 7 траектория будет состоять из чисел 21, 23, 26.
Ответ напишите в комментариях этого поста
Данная задача была взята с открытого банка заданий ОГЭ по информатике.
