Question

Исполнитель М17 преобразует число на экране с помощью трёх команд:
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3

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

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

Accepted Answer

60

Answer

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

Обозначим через $R(n)$ количество способов получить число $n$ из числа 2.

Для каждого числа $n$ можно прийти тремя путями:
- из $n-1$ (команда «+1»);
- из $n-2$ (команда «+2»);
- из $n/3$ (команда «×3», если $n$ делится на 3).

Таким образом, рекуррентное соотношение:
$$R(n) = R(n-1) + R(n-2) + \begin{cases} R(n/3) & 	ext{если } 3 \mid n \ 0 & 	ext{иначе} \end{cases}$$

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

Вычислим значения:
- $R(2) = 1$
- $R(3) = R(2) = 1$
- $R(4) = R(3) + R(2) = 1 + 1 = 2$
- $R(5) = R(4) + R(3) = 2 + 1 = 3$
- $R(6) = R(5) + R(4) + R(2) = 3 + 2 + 1 = 6$
- $R(7) = R(6) + R(5) = 6 + 3 = 9$
- $R(8) = R(7) + R(6) = 9 + 6 = 15$
- $R(9) = R(8) + R(7) + R(3) = 15 + 9 + 1 = 25$
- $R(10) = R(9) + R(8) = 25 + 15 = 40$

Для этапа 8 → 10:
- $R(9) = R(8) + R(7) + R(3) = 15 + 9 + 1 = 25$
- $R(10) = R(9) + R(8) = 25 + 15 = 40$

Но нам нужно количество программ, ведущих из 8 в 10. Переопределим: пусть $S(a, b)$ — количество программ, преобразующих $a$ в $b$.

$$S(a, b) = \begin{cases} 0 & 	ext{если } a > b \ 1 & 	ext{если } a = b \ S(a+1, b) + S(a+2, b) + S(a \cdot 3, b) & 	ext{если } a < b \end{cases}$$

Вычислим:
- $S(8, 10) = S(9, 10) + S(10, 10) + S(24, 10) = S(9, 10) + 1 + 0$
- $S(9, 10) = S(10, 10) + S(11, 10) + S(27, 10) = 1 + 0 + 0 = 1$
- $S(8, 10) = 1 + 1 = 2$

- $S(10, 12) = S(11, 12) + S(12, 12) + S(30, 12) = S(11, 12) + 1 + 0$
- $S(11, 12) = S(12, 12) + S(13, 12) + S(33, 12) = 1 + 0 + 0 = 1$
- $S(10, 12) = 1 + 1 = 2$

Итоговое количество программ:
$$S(2, 8) 	imes S(8, 10) 	imes S(10, 12) = 15 	imes 2 	imes 2 = 60$$

Решение на Python:

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

print(f(2, 8) * f(8, 10) * f(10, 12))
```

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