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