Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(М. Шагитов) У исполнителя Калькулятор имеются три команды, которым присвоены номера:
Укажите количество программ, которые преобразуют число 4 в число 68 и при этом траектория вычислений программы содержит число 16 или 32, но не оба эти числа одновременно.
1. прибавь 3Выполняя первую из них, исполнитель увеличивает число на экране на 3, выполняя вторую – увеличивает на 5, выполняя третью – умножает число на 2.
2. прибавь 5
3. умножь на 2
Укажите количество программ, которые преобразуют число 4 в число 68 и при этом траектория вычислений программы содержит число 16 или 32, но не оба эти числа одновременно.
Ответ:
15570
Шаблон решения на 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))