ЕГЭ 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.

Ответ напишите в комментариях этого поста

Данная задача была взята с открытого банка заданий ОГЭ по информатике.