Question

У исполнителя Утроитель две команды:
1. прибавь 1
2. умножь на 3

Первая команда увеличивает число на экране на 1, вторая утраивает его. Программа для Утроителя — это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 34?

Accepted Answer

20

Answer

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

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

**Ключевые наблюдения:**

1. Если $n$ не делится на 3, то единственный способ получить $n$ из меньшего числа — прибавлять единицы. Поэтому $R(n) = R(t(n))$, где $t(n)$ — наибольшее число, не превосходящее $n$ и делящееся на 3.

2. Если $n$ делится на 3, то $n$ можно получить двумя способами:
   - из числа $n/3$ умножением на 3;
   - из числа $n-1$ прибавлением 1.
   
   Следовательно, $R(n) = R(n/3) + R(n-1)$.

3. Для чисел, не кратных 3, значение $R(n)$ совпадает со значением для ближайшего меньшего числа, кратного 3.

Вычислим значения для всех чисел, кратных 3, не превосходящих 34:

- $R(3) = 1$ (единственный путь: $2 	o 3$ прибавлением 1)
- $R(6) = R(2) + R(5) = 1 + 1 = 2$
- $R(9) = R(3) + R(8) = 1 + 2 = 3$
- $R(12) = R(4) + R(11) = 1 + 3 = 4$
- $R(15) = R(5) + R(14) = 1 + 4 = 5$
- $R(18) = R(6) + R(17) = 2 + 5 = 7$
- $R(21) = R(7) + R(20) = 2 + 7 = 9$
- $R(24) = R(8) + R(23) = 2 + 9 = 11$
- $R(27) = R(9) + R(26) = 3 + 11 = 14$
- $R(30) = R(10) + R(29) = 3 + 14 = 17$
- $R(33) = R(11) + R(32) = 3 + 17 = 20$
- $R(34) = R(33) = 20$

**Рекурсивное решение на 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)

print(f(2, 34))
```

Функция $f(x, y)$ вычисляет количество программ, преобразующих $x$ в $y$. На каждом шаге рассматриваются две возможности: прибавить 1 или умножить на 3. Если текущее число превышает целевое, путь невозможен (возвращаем 0). Если числа совпадают, найден один способ (возвращаем 1).

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