Задание 23

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

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

---

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

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

1. Прибавить 1
2. Умножить на 2

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

Результат: 28

23_2:

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

1. прибавь 1
2. умножь на 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_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