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