Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(И. Женецкий) Исполнитель Калькулятор преобразует число, записанное на экране. У исполнителя есть две команды, которым присвоены номера:
Сколько существует программ, для которых при исходном числе 50 результатом является число 1?
1. Вычти 3Первая из них уменьшает число на экране на 3, вторая заменяет число на экране на целую часть от деления числа на 7. Программа для исполнителя – это последовательность команд.
2. Найди целую часть от деления на 7
Сколько существует программ, для которых при исходном числе 50 результатом является число 1?
Ответ:
6
Шаблон решения на 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))