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