Question

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

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

Программа — это последовательность команд. Траектория вычислений — последовательность результатов выполнения всех команд.

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

Accepted Answer

504

Answer

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

**Способ 1: Динамическое программирование**

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

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

Базовый случай: $R(1) = 1$.

Вычислим последовательно:

| $n$ | $R(n)$ | Вычисление |
|---|---|---|
| 1 | 1 | базовый случай |
| 2 | 1 | $R(1)$ |
| 3 | 3 | $R(2) + R(1) + R(1)$ |
| 4 | 4 | $R(3) + R(2)$ |
| 5 | 7 | $R(4) + R(3)$ |
| 6 | 12 | $R(5) + R(4) + R(2)$ |
| 7 | 19 | $R(6) + R(5)$ |
| 8 | 31 | $R(7) + R(6)$ |
| 9 | 53 | $R(8) + R(7) + R(3)$ |
| 10 | 84 | $R(9) + R(8)$ |
| 11 | 84 | $R(10)$ |
| 12 | 168 | $R(11) + R(10)$ |
| 13 | 168 | $R(12)$ |
| 14 | 336 | $R(13) + R(12)$ |
| 15 | 504 | $R(14) + R(13)$ |

Таким образом, $R(15) = 504$.

**Способ 2: Произведение путей**

Количество программ, преобразующих 1 в 15 через 10 и 12, равно произведению:
- количество программ из 1 в 10: $R(10) = 84$
- количество программ из 10 в 12: 2 (программы: 11, 2)
- количество программ из 12 в 15: 3 (программы: 111, 12, 21)

Общее количество: $84 	imes 2 	imes 3 = 504$.

**Способ 3: Рекурсивное решение на Python**

```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(1, 10) * f(10, 12) * f(12, 15)
print(result)
```

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