Динамическое программирование Исполнитель Вычислитель преобразует число на экране компьютера. У него есть две команды: Прибавь 1 Умножь на 2 Программа Вычислителя – это…
Динамическое программирование Исполнитель Вычислитель преобразует число на экране компьютера. У него есть две команды: Прибавь 1 Умножь на 2 Программа Вычислителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 5 результатом является число 18?
Для решения данной задачи с использованием динамического программирования, мы можем определить функцию DP[i], которая показывает количество способов получить число i с использованием только команд "Прибавь 1" и "Умножь на 2".
Для начала, инициализируем массив DP размером 19 (ведь мы рассматриваем числа от 0 до 18) и заполним его нулями, кроме DP[5] = 1, так как при исходном числе 5 у нас один способ получить 5 – это не выполнять никаких действий.
Затем пройдем по всем числам от 5 до 18 и для каждого числа i рассчитаем количество способов получить число i в зависимости от предыдущих чисел. Мы можем получить число i из числа i - 1 выполнением команды "Прибавь 1" и из числа i // 2 (целая часть от деления на 2) выполнением команды "Умножь на 2".
DP = [0] * 19
DP[5] = 1
for i in range(6, 19):
DP[i] = DP[i - 1] + DP[i // 2]
# Результатом будет значение DP[18], так как именно это число мы стремимся получить
print("Количество программ:", DP[18])
После проведения расчетов мы получим количество программ, для которых при исходном числе 5 результатом является число 18.
