Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(А. Минак) У исполнителя Калькулятор имеются три команды, которые обозначены латинскими буквами:
А. Прибавь 1Программа для исполнителя – это последовательность команд, каждая из которых изменяет число. Сколько существует программ c разными траекториями, для которых при исходном числе 82 результатом является число 124, и при этом траектория вычислений содержит число 95 и число 103? Траектория вычисления программы – это последовательность результатов выполнения всех команд программы. Например, при исходном числе 17 траектория вычислений программы CBA будет состоять из чисел 18, 26, 27.
B. Прибавь младшую цифру
C. Прибавь старшую цифру
Ответ:
20709
Шаблон решения на Python
# === Задание 23: Динамическое программирование (Количество программ) ===
def f(cur, target, avoid=None):
if cur > target or (avoid and cur == avoid): return 0
if cur == target: return 1
return f(cur + 1, target, avoid) + f(cur * 2, target, avoid)
# Траектория из A в B (через обязательную точку):
print("Количество программ:", f(2, 12) * f(12, 30))