Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(А. Богданов) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть четыре команды, которым присвоены номера:
1. прибавь 1Первая из них увеличивает число на экране на 1, вторая - увеличивает его на 3, третья - уменьшает на 1, четвёртая - уменьшает на 3. Программа для исполнителя – это последовательность команд. Сколько существует программ, для которых при исходном числе 42 результатом будет являться число 42, при этом траектория вычисления может содержать только числа от 40 до 49, притом каждое число не более одного раза.
2. прибавь 3
3. вычти 1
4. вычти 3
Ответ:
85
Шаблон решения на 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))