Question

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

1. Прибавить 1
2. Прибавить 3
3. Умножить на 3

Требуется найти количество программ, которые преобразуют исходное число 3 в число 18, при условии, что траектория вычислений не проходит через числа 9 и 15.

Accepted Answer

31

Answer

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

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

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

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

print(f(3, 18))
```

Вычисляем $f(3, 18)$, которое даёт количество всех допустимых программ.

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