Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(П. Тюрин) У исполнителя имеются две команды, которые обозначены номерами:
2 результатом является число 70, причём
а) команда сложения не применяется более двух раз подряд;
б) траектория вычислений проходит либо через числа 8 и 16, либо через число 32 (но не через все три числа одновременно).
Сколько различных чисел содержится во всех таких траекториях вычислений?
1. Умножить на 2Первая команда умножает число на 2, вторая увеличивает его на 3. Программа для исполнителя – это последовательность команд. Рассматриваются все программы, в которых при исходном числе
2. Прибавить 3
2 результатом является число 70, причём
а) команда сложения не применяется более двух раз подряд;
б) траектория вычислений проходит либо через числа 8 и 16, либо через число 32 (но не через все три числа одновременно).
Сколько различных чисел содержится во всех таких траекториях вычислений?
Ответ:
12
Шаблон решения на 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))