Каталог: Задание №23. Динамическое программирование (Количество программ)

Банк задач: 374 Формат ЕГЭ 2026 Базовый (1 балл) 2-3 мин Шаблоны решений на Python

Выберите номер задания ЕГЭ:

№1 №2 №3 №4 №5 №6 №7 №8 №9 №10 №11 №12 №13 №14 №15 №16 №17 №18 №19 №20 №21 №22 №23 №24 №25 №26 №27

Спецификация и суть задания №23

Тема кодификатора Исполнитель преобразует число А в В, обязательные и избегаемые этапы

Сложность и баллы Базовый (1 балл)

Рекомендуемое время 2-3 мин

Инструменты решения Python def, Рекурсия f(curr, target)

Подсчет количества различных программ, переводящих число A в число B с обязательным прохождением через число C и избеганием числа D. Решается в 6 строк кода.

Основные прототипы и разновидности

Тип 1: Обязательный и избегаемый этапы

Разбиение на произведение f(A, C) * f(C, B) с проверкой curr == D: return 0.

Теоретический фундамент и алгоритмы

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, раздели на 2), условие остановки: if curr < target: return 0.

Частые ошибки и экзаменационные ловушки

Ошибка: Сложить результаты вместо умножения: f(A, C) + f(C, B)
По правилу комбинаторного произведения число путей перемножается!

Правильно: Всегда перемножать этапы: f(A, C) * f(C, B)

ГРОБ №23: Ограничение на количество применений конкретной команды

Команда '*2' может быть применена не более 2 раз.

Алгоритм решения: Добавьте третий параметр-счетчик: `def f(curr, target, count_mult):`.

Практические задачи из банка КИМ (Всего: 374)

Решать в песочнице СмартКИМ

Задача #9040 №23 ЕГЭ