Question

Исполнитель преобразует число на экране с помощью трёх команд:

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

Сколько существует программ, которые преобразуют исходное число 20 в число 3?

Accepted Answer

76

Answer

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

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

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

```python
def f(x, y):
    if x < y:
        return 0
    if x == y:
        return 1
    return f(x - 2, y) + f(x - 3, y) + f(x // 3, y)

print(f(20, 3))
```

Вычисляем $f(20, 3)$, раскрывая рекурсию по всем возможным последовательностям команд, пока не достигнем числа 3 или не выйдем за его пределы.

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