Question

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

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

Программа — это последовательность команд. Сколько существует программ, которые преобразуют исходное число 2 в число 12 и при этом траектория вычислений содержит числа 9 и 11?

Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 132 при исходном числе 7 траектория будет состоять из чисел 8, 10, 30.

Accepted Answer

150

Answer

Идея решения: найти количество программ, ведущих из 2 в 12 через обязательные промежуточные значения 9 и 11, используя динамическое программирование.

Обозначим $R(n)$ — количество программ, преобразующих число 2 в число $n$.

Рекуррентное соотношение:
$$R(n) = R(n-1) + R(n-2) + R(n/3) 	ext{ (если } n 	ext{ кратно } 3)$$

Начальное условие: $R(2) = 1$.

Вычислим значения:

- $R(2) = 1$
- $R(3) = R(2) = 1$
- $R(4) = R(3) + R(2) = 2$
- $R(5) = R(4) + R(3) = 3$
- $R(6) = R(5) + R(4) + R(2) = 6$
- $R(7) = R(6) + R(5) = 9$
- $R(8) = R(7) + R(6) = 15$
- $R(9) = R(8) + R(7) + R(3) = 25$
- $R(10) = R(9) + R(8) = 40$
- $R(11) = R(10) + R(9) = 65$
- $R(12) = R(11) + R(10) + R(4) = 107$

Однако нам нужны программы, проходящие через 9 и 11 в указанном порядке. Применим принцип произведения:

Количество программ = (программы из 2 в 9) × (программы из 9 в 11) × (программы из 11 в 12)

Вычислим каждый множитель:

**Из 2 в 9:** $R(9) = 25$ (как вычислено выше).

**Из 9 в 11:** применим рекуррентность с начальным условием $R(9) = 1$:
- $R(10) = R(9) + R(8) = 1 + 1 = 2$
- $R(11) = R(10) + R(9) = 2 + 1 = 3$

Получить 11 из 9 можно 3 способами.

**Из 11 в 12:** применим рекуррентность с начальным условием $R(11) = 1$:
- $R(12) = R(11) + R(10) = 1 + 1 = 2$

Получить 12 из 11 можно 2 способами.

Итоговое количество программ: $25 	imes 3 	imes 2 = 150$.

Проверим рекурсивным подсчётом:

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

result = f(2, 9) * f(9, 11) * f(11, 12)
print(result)
```

Вывод: 150.

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