Question

Исполнитель преобразует число на экране с помощью трёх команд:
- **A.** Вычти 1
- **B.** Вычти 2
- **C.** Найди целую часть от деления на 3

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

Accepted Answer

64

Answer

Идея решения: разбить задачу на два этапа — найти количество путей от 16 к 11, затем от 11 к 6, и перемножить результаты.

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

Рекуррентное соотношение:
- Если $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 // 3, y)$ (применяем одну из трёх команд и считаем пути из полученного числа).

Общее количество программ, проходящих через 11:
$$f(16, 11) 	imes f(11, 6)$$

```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 // 3, y)

result = f(16, 11) * f(11, 6)
print(result)
```

Вычисляем:
- $f(16, 11)$ — количество путей от 16 к 11.
- $f(11, 6)$ — количество путей от 11 к 6.
- Произведение даёт искомое количество программ.

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