Question

Исполнитель А16 преобразует число на экране с помощью трёх команд:

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

Программа — это последовательность команд. Найти количество программ, которые преобразуют исходное число 3 в число 12, при условии, что траектория вычислений содержит число 10.

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

Accepted Answer

60

Answer

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

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

Рекуррентные соотношения:
- Если $n$ нечётно: $R(n) = R(n-1) + R(n-2)$ (только команды +1 и +2)
- Если $n$ чётно: $R(n) = R(n-1) + R(n-2) + R(n/2)$ (команды +1, +2 и ×2)

Аналогично для $P(n)$.

Вычислим $R(n)$ для $n$ от 3 до 10:

$$R(3) = 1$$
$$R(4) = R(3) = 1$$
$$R(5) = R(4) + R(3) = 1 + 1 = 2$$
$$R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4$$
$$R(7) = R(6) + R(5) = 4 + 2 = 6$$
$$R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11$$
$$R(9) = R(8) + R(7) = 11 + 6 = 17$$
$$R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30$$

Вычислим $P(n)$ для $n$ от 10 до 12:

$$P(10) = 1$$
$$P(11) = P(10) = 1$$
$$P(12) = P(11) + P(10) = 1 + 1 = 2$$

Итоговое количество программ: $30 	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 * 2, y)

print(f(3, 10) * f(10, 12))
```

Решение на PascalABC:

```pascal
function f(a, b: integer): integer :=
    a > b ? 0 : a = b ? 1 :
    f(a + 1, b) + f(a + 2, b) + f(a * 2, b);

print(f(3, 10) * f(10, 12));
```

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