ЕГЭ по информатике 2020, часть 1, № 22 , динамическое программирование

ЕГЭ по информатике 2020, вариант Москва
Часть 1, № 22
Динамическое программирование
Задание взято с сайта
http://kotolis.ru/realegeinf_2020

№ 22
Условие.
У исполнителя есть три команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на З
3. Прибавить 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 3, третья увеличивает на 2.
Сколько существует программ, которые преобразуют исходное число 3 в число 14 и при этом траектория вычислении содержит число 9?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10,30.
-------------------------------------

Во первых строках хочу сказать:
Господа школьники (репетиторы и прочие заинтересованные лица)!
Читайте лекции Котова по динамическому программированию для школьников.
Они есть в интернете, есть на этом форуме (в разделе Алгоритмы),
вот они на яндекс-диске:
https://yadi.sk/i/dfL27HNQZhLiaw

Далее всё изложение будет идти согласно этой прекрасной книге.
По сути, возьмём решение Примера 1 на стр. 6 (задача про лестницу) и приспособим его к задаче №22.

Пример #1.
Определить, сколькими различными способами можно подняться на 10-ю ступеньку лестницы, если за один шаг можно подниматься на следующую ступеньку или через одну.

Пусть K(10)- количество способов подъема на 10 ступеньку.
Определим подзадачу K(i) нашей задачи, как количество способов подъема на i-ю ступеньку.
Исходя из условия задачи, на 10 ступеньку можно подняться непосредственно с 8-й и 9-й ступенек.
Поэтому, если мы знаем количество способов подъема K(8) и K(9) на 8 и 9 ступеньки соответственно, то количество способов подъема на 10 ступеньку может быть определено как K(10) = K(8) + K(9).
Аналогичное соотношение справедливо для любой ступеньки i, начиная с третьей, т.е.
K(i) = K(i - 2) + K(i - 1).
Осталось определить значения K(1) и K(2), которые равны: K(1) = 1, K(2) = 2.

Следовательно, для решения задачи достаточно одномерной таблицы с 10 - ю элементами, для которой необходимо последовательно вычислить значения элементов таблицы согласно приведенным выше рекуррентным соотношениям. Сделаем это посредством последовательных вычислений.
K[1] := 1;
K[2] := 2;
For i := 3 to 10 do
K[i] := K[i - 1] + K[i - 2]

Протрассируем предложенный алгоритм, вычисляя элементы одномерного массива.
Способ подняться на первую ступеньку - один (K(1) = 1), способов подняться на вторую ступеньку - 2 (K(2) = 2).
Каждый элемент массива, начиная с третьего, получается как сумма двух предыдущих элементов (K(i) = K(i - 2) + K(i - 1)).

K(1)	K(2)	K(3)	K(4)	K(5)	K(6)	K(7)	K(8)	K(9)	K(10)
1	2	3	5	8	13	21	34	55	89

Итого 89 способов подняться на 10-ю ступеньку, на каждом шаге добавляя либо +1, либо +2 ступеньки.

Сообщение отредактировано: swf - 21.07.20, 20:06

Решение.
Вначале разберёмся с командой умножения на 3, которой не было в задаче про лестницу.
Её можно применить ровно один раз – получить 9 из 3. 3 * 4 = 12, перескакиваем через число 9, которое должно присутствовать в траектории. Запомним, что 9 можно получить из 3 1 способом с помощью команды 2.
Получили задачу получения 14 из 3 с помощью команд +1 и +2, и чтобы в траектории была 9. Разделим эту задачу на две подзадачи.

Подзадача 1, получение числа 9 из числа 3
Задача совершенно аналогична задаче про лестницу.
Только там мы начинали с пола (0-й ступеньки), а здесь начинаем с 3-й ступеньки.
K(i) = K(i–2) + K(i–1), i >= 6.
K(4) = 1, K(5) = 2.

Поэтому таблица выглядит так:

K(4)	K(5)	K(6)	K(7)	K(8)	K(9)
1	2	3	5	8	13

Итого 1 + 13 = 14 способов получения числа 9.

Подзадача 2, получение числа 14 из числа 9
Пусть мы уже находимся на 9-й ступеньке, неважно, как мы туда попали.
К слову, это очень важное свойство нашей задачи! Нам не нужно помнить, как мы попали в текущее состояние. Если бы это было не так (система имела последействие), то задачу нельзя было бы решать методом динамического программирования.
K(i) = K(i–2) + K(i–1), i >= 12.
K(10) = 1, K(11) = 2.

Таблица:

K(10)	K(11)	K(12)	K(13)	K(14)
1	2	3	5	8

Итого 8 способов набрать 14, начиная с 9 и используя команды +1 и +2.

Теперь соединяем решения обеих подзадач в одно: с 3-й ступеньки попасть на 9-ю можно 14 способами, с 9-й ступеньки подняться на 14-ю можно 8 способами.
Итого 14 * 8 = 112 способов (программ).

Ответ: 112 .

Сообщение отредактировано: swf - 21.07.20, 19:51