Задание №23 — Поиск количества программ

Решение:

Все три команды строго увеличивают число (при исходном числе 2 прибавление единицы, удвоение и возведение в квадрат дают большее число), поэтому траектория растёт и «перепрыгнуть» цель, а потом вернуться к ней невозможно. Значит, количество программ удобно считать рекурсивно с конца.

Обозначим через $R(a)$ число программ, переводящих $a$ в 20 так, чтобы дальше по траектории не встретилось 11. Тогда $R(20) = 1$ (пустая программа), $R(a) = 0$ при $a \gt 20$ (цель проскочена) и $R(11) = 0$ — запрещённое число обнуляет весь путь, ведь если траектория попала в 11, программа уже не годится. В остальных случаях первый шаг делается одной из трёх команд, и варианты складываются: $R(a) = R(a + 1) + R(2a) + R(a^2)$.

Считая от больших чисел к меньшим (или просто с кэшированием), получаем $R(2) = 37$. Запрет на 11 существенно режет перебор: например, ветка $10 \to 11$ полностью отбрасывается, и из 10 в 20 остаётся только удвоение.

from functools import lru_cache

@lru_cache(None)
def R(a):
    if a == 11 or a > 20:
        return 0
    if a == 20:
        return 1
    return R(a + 1) + R(2 * a) + R(a * a)

print(R(2))   # 37

Ответ: 37