Question

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

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

Программа — это последовательность команд. Найти количество программ, которые:
- начинают с числа 4;
- завершаются числом 19;
- проходят через число 15;
- не содержат число 6 в траектории.

Accepted Answer

320

Answer

Идея решения: разбить задачу на два этапа — путь от 4 до 15 и от 15 до 19, исключив недопустимые значения, затем перемножить количества программ для каждого этапа.

Заметим, что число 6 недопустимо на всей траектории. Разделим вычисление на две части:
- количество программ, ведущих из 4 в 15 без прохождения через 6;
- количество программ, ведущих из 15 в 19 без прохождения через 6.

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

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

result = f(4, 15) * f(15, 19)
print(result)
```

Функция $f(x, y)$ работает следующим образом:
- если $x > y$ или $x = 6$, возвращаем 0 (недопустимое состояние);
- если $x = y$, возвращаем 1 (достигли цели);
- иначе суммируем количества путей через все три команды.

Вычисляем $f(4, 15)$ — число программ из 4 в 15, затем $f(15, 19)$ — число программ из 15 в 19. Итоговый результат — произведение этих значений.

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