Question

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

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

Программа — это последовательность команд. Найти количество программ, которые преобразуют исходное число 3 в число 18, при условии, что траектория вычислений содержит число 14 и не содержит число 8.

Траектория вычислений — последовательность результатов выполнения всех команд программы.

Accepted Answer

360

Answer

Идея решения: разбить задачу на два независимых этапа — путь от 3 до 14 (избегая 8) и путь от 14 до 18, затем перемножить количества программ.

Используем рекурсивную функцию `f(x, y)`, которая подсчитывает количество программ, преобразующих число `x` в число `y`, при условии, что траектория не проходит через 8.

Базовые случаи:
- Если `x > y` или `x == 8`, то путей нет (возвращаем 0).
- Если `x == y`, то найден один путь — пустая программа (возвращаем 1).

Рекурсивный случай: из числа `x` можно перейти в `x + 1`, `x + 2` или `2x`, поэтому суммируем количества путей из каждого из этих чисел в `y`.

Финальный ответ — произведение количества программ от 3 до 14 и от 14 до 18.

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

print(f(3, 14) * f(14, 18))
```

Вычисления:
- `f(3, 14)` подсчитывает пути от 3 до 14, не проходящие через 8.
- `f(14, 18)` подсчитывает пути от 14 до 18 (число 8 уже позади, поэтому ограничение не влияет).
- Произведение дает общее количество программ.

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