Базовый (1 балл)
Время: 2-3 мин
Python def
Рекурсия f(curr, target)
Все задачи №{ topic_num } в каталоге
Задание №23. Динамическое программирование (Количество программ)
Тема: Исполнитель преобразует число А в В, обязательные и избегаемые этапы
Подсчет количества различных программ, переводящих число A в число B с обязательным прохождением через число C и избеганием числа D. Решается в 6 строк кода.
1. Рекурсивная функция в 5 строк:
def f(curr, target):
if curr == target: return 1
if curr > target or curr == 13: return 0 # 13 — избегаемое число
return f(curr + 1, target) + f(curr * 2, target)Если в условии есть обязательный этап C (траектория содержит число C), ответ равен $f(A, C) \cdot f(C, B)$.
Разновидности и прототипы задания на экзамене
Тип 1: Обязательный и избегаемый этапы
Разбиение на произведение `f(A, C) * f(C, B)` с проверкой `curr == D: return 0`.
Боевой шаблон решения на Python
Запустить код в онлайн-песочнице# === Боевой шаблон Задания №23 на Python ===
def f(curr, target):
if curr == target:
return 1
# Если вышли за границу или попали в избегаемое число:
if curr > target or curr == 17: # 17 — число, которого НЕ должно быть
return 0
# Суммируем все возможные команды исполнителя:
return f(curr + 1, target) + f(curr + 2, target) + f(curr * 3, target)
# Если траектория содержит число 10 (путь от 2 до 25):
ans = f(2, 10) * f(10, 25)
print("Количество программ:", ans)Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Сложить результаты вместо умножения: f(A, C) + f(C, B)
По правилу комбинаторного произведения число путей перемножается!Как делать ПРАВИЛЬНО:
Правильно: Всегда перемножать этапы: f(A, C) * f(C, B)
ГРОБ
ГРОБ №23: Ограничение на количество применений конкретной команды
Команда '*2' может быть применена не более 2 раз.
Как обойти ловушку: Добавьте третий параметр-счетчик: `def f(curr, target, count_mult):`.
Лайфхаки и подводные камни на экзамене:
- Если команды уменьшают число (например, вычти 1, раздели на 2), условие остановки: `if curr < target: return 0`.