Question

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

1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

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

Accepted Answer

200

Answer

Идея решения: разбить задачу на два этапа — путь от 3 до 8 и путь от 8 до 18, исключив траектории, проходящие через 13.

Используем рекурсивную функцию, которая подсчитывает количество способов достичь целевого числа из текущего, соблюдая ограничения:
- если текущее число превышает целевое или равно 13, путь невозможен;
- если текущее число равно целевому, найден один способ;
- иначе суммируем количества способов для всех трёх команд.

Общее количество программ равно произведению:
- количество путей от 3 до 8 (без прохождения через 13);
- количество путей от 8 до 18 (без прохождения через 13).

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

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

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

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