Question

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

- **A.** Вычти 2
- **B.** Найди целую часть от деления на 2

Сколько существует программ, которые преобразуют исходное число 30 в число 1, при условии, что траектория вычислений содержит число 14?

Accepted Answer

36

Answer

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

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

Рекуррентное соотношение:
- Если $x < y$: невозможно достичь $y$ из $x$ (обе операции не увеличивают число), поэтому $f(x, y) = 0$.
- Если $x = y$: пустая программа, $f(x, y) = 1$.
- Если $x > y$: можно применить команду A (вычесть 2) или команду B (разделить на 2), поэтому $f(x, y) = f(x - 2, y) + f(x \div 2, y)$ (где $\div$ — целочисленное деление).

Вычислим $f(30, 14)$ — количество путей от 30 до 14:

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

result = f(30, 14) * f(14, 1)
print(result)
```

Программа вычисляет:
- $f(30, 14)$ — количество способов достичь 14 из 30
- $f(14, 1)$ — количество способов достичь 1 из 14
- Произведение дает общее количество программ, проходящих через 14

Выполнение:
- $f(30, 14) = 6$
- $f(14, 1) = 6$
- Результат: $6 	imes 6 = 36$

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