Question

У исполнителя Удвоитель две команды:
1. прибавь 1
2. умножь на 2

Первая команда увеличивает число на экране на 1, вторая удваивает его. Программа — это последовательность команд. Сколько существует программ, которые число 3 преобразуют в число 23?

Accepted Answer

22

Answer

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

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

Базовые случаи:
- если $x = y$, то существует ровно одна программа (пустая последовательность), поэтому $f(x, y) = 1$;
- если $x > y$, то достичь $y$ из $x$ невозможно, поэтому $f(x, y) = 0$.

Рекуррентное соотношение: из числа $x$ можно перейти либо в $x + 1$ (команда 1), либо в $2x$ (команда 2). Таким образом:

$$f(x, y) = f(x + 1, y) + f(2x, y)$$

Вычислим $f(3, 23)$:

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

print(f(3, 23))
```

Программа рекурсивно перебирает все возможные последовательности команд, начиная с числа 3, и подсчитывает те, которые приводят к 23.

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