Задание №23: Динамическое программирование (Количество программ)
Основные типы и прототипы задания №23:
Количество программ преобразования чисел
Обязательные и избегаемые этапы траектории
Условие задания
(ЕГКР-2024) У исполнителя имеются три команды, которые обозначены латинскими буквами:
A. Вычти 1Первая команда уменьшает число на экране на 1, вторая команда уменьшает это число на 6, третья команда делит число нацело на 2. Программа для исполнителя – это последовательность команд. Сколько существует таких программ, которые исходное число 34 преобразуют в число 6, и при этом траектория вычислений содержит числа 19 и 29 и не содержит числа 24?
B. Вычти 6
C. Найди целую часть от деления на 2
Ответ:
115
Шаблон решения на 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))