5 Избегаемое число — отсекаем

Избегаемое число — отсекаем

Если траектория не должна содержать некоторое число K, добавляем его в условие-тупик: попав на K, программа считается несостоявшейся.

def f(x, y):
    if x > y or x == 25: return 0    # цель недостижима ИЛИ попали на запретное 25
    if x == y: return 1
    return f(x + 1, y) + f(x * 2, y)

print(f(2, 14) * f(14, 29))          # через 14, но минуя 25

Пример: обязательная точка и запрет вместе

Условие

Исполнитель имеет команды «прибавить 1» и «умножить на 2». Сколько программ превращают число 2 в число 29, если траектория обязана содержать 14 и не содержит числа, которого достигать нельзя?

Собираем всё вместе: обязательную точку 14 — через произведение, запрет — в тупик.

def f(x, y):
    if x > y or x == 25: return 0
    if x == y: return 1
    return f(x + 1, y) + f(x * 2, y)

print(f(2, 14) * f(14, 29))          # 13

Ответ: 13

💡 Убывающие команды

Иногда команды уменьшают число (например, «−1» и «целочелённо ÷2»). Тогда цель меньше старта, и тупик — это x < y (проскочили вниз). Схема та же:

def f(x, y):

if x < y: return 0

if x == y: return 1

return f(x - 1, y) + f(x // 2, y)