Question

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

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

Найти количество программ, которые преобразуют исходное число 7 в число 20, при условии, что траектория содержит число 14 и не содержит число 15.

Accepted Answer

18

Answer

Идея решения: разбить задачу на два этапа — путь от 7 до 14 (исключая 15) и путь от 14 до 20 (исключая 15), затем перемножить количества программ для каждого этапа.

Ключевое наблюдение: число 15 недопустимо на всей траектории, поэтому при достижении 15 ветвь вычисления прерывается. Число 14 обязательно должно быть посещено, поэтому мы считаем пути через 14.

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

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

result = f(7, 14) * f(14, 20)
print(result)
```

Логика работы:
- `f(7, 14)` подсчитывает количество программ, ведущих из 7 в 14 без посещения 15.
- `f(14, 20)` подсчитывает количество программ, ведущих из 14 в 20 без посещения 15.
- Общее количество программ — произведение этих двух значений, так как любая программа из 7 в 20 через 14 составляется из независимых участков.

Условие `x == 15` гарантирует, что число 15 не посещается. Условие `x > y` останавливает рекурсию, если число превышает целевое.

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