Question

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

- **A.** Прибавить 1
- **B.** Прибавить 2
- **C.** Умножить на 2

Программа — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 4 в число 15, при этом траектория вычислений содержит оба числа: 11 и 13?

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

Accepted Answer

100

Answer

Идея решения: разбить задачу на три независимых этапа — от 4 к 11, от 11 к 13 и от 13 к 15 — и перемножить количества программ для каждого этапа.

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

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

Поскольку траектория должна содержать оба числа 11 и 13 в указанном порядке, общее количество программ равно:

$$f(4, 11) 	imes f(11, 13) 	imes f(13, 15)$$

Реализация:

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

result = f(4, 11) * f(11, 13) * f(13, 15)
print(result)
```

Вычисляем:
- $f(4, 11)$ — количество путей от 4 к 11: 35
- $f(11, 13)$ — количество путей от 11 к 13: 2
- $f(13, 15)$ — количество путей от 13 к 15: 5

Итоговый результат: $35 	imes 2 	imes 5 = 100$.

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