Задание 13 ЕГЭ: убывающие команды

Убывающие команды: количество программ. Тема номера — количество программ исполнителя. Ниже — пример с ответом и решением; кнопкой под ним можно решить такую же задачу с другими числами, ответ проверится сразу.

Пример

Исполнитель преобразует число на экране. У исполнителя есть две команды, которые обозначены буквами:

А. Вычесть 2
Б. Разделить нацело на 2

Первая команда уменьшает число на 2, вторая заменяет число на целую часть от деления на 2. Программа для исполнителя — последовательность команд.

Сколько существует программ, для которых при исходном числе 89 результатом является число 3, и при этом траектория вычислений содержит число 18 и не содержит числа 48?

Траектория вычислений — последовательность результатов выполнения всех команд программы.

Решение

Обе команды уменьшают число, поэтому программ конечное число. Путь «89 → 18 → 3» делим на две части и перемножаем количества; число 48 запрещено — из него путей нет. Важно: деление нацело может «перепрыгнуть» через 18, поэтому считаем именно пути, проходящие через 18.

Ответ: 232.

def f(x, y):
    if x == y:
        return 1
    if x < y or x == 48:
        return 0
    return f(x - 2, y) + f(x // 2, y)

print(f(89, 18) * f(18, 3))

Решить такую задачу — новый вариант с проверкой