Question

Исполнитель преобразует число на экране. Доступны три команды:
- **A**: прибавить 1
- **B**: умножить на 2
- **C**: умножить на 3

Программа — это последовательность команд. Найти количество программ, которые преобразуют исходное число 2 в число 39, при условии, что траектория вычислений не содержит число 14.

Траектория вычислений — это последовательность всех промежуточных результатов. Например, для программы ABC при исходном числе 7 траектория: 8, 16, 48.

Accepted Answer

188

Answer

Идея решения: использовать рекурсию с мемоизацией, подсчитывая количество способов достичь целевого числа 39 из текущего числа, избегая запретного значения 14.

Обозначим через $f(x, y)$ количество программ, преобразующих число $x$ в число $y$ без прохождения через 14.

Рекуррентное соотношение:
- Если $x > y$ или $x = 14$: $f(x, y) = 0$ (превышена цель или попали в запретное число).
- Если $x = y$: $f(x, y) = 1$ (достигли цели, пустая программа).
- Иначе: $f(x, y) = f(x+1, y) + f(x \cdot 2, y) + f(x \cdot 3, y)$ (применяем одну из трёх команд).

```python
def f(x, y):
    if x > y or x == 14:
        return 0
    if x == y:
        return 1
    return f(x + 1, y) + f(x * 2, y) + f(x * 3, y)

print(f(2, 39))
```

Функция рекурсивно перебирает все возможные пути от 2 к 39, отсекая ветви, которые либо превышают целевое значение, либо проходят через 14.

Задание №23Алгоритмы и исполнителиЕГЭ по информатике