Задание №5 — Алгоритмы и программирование

Решение.

Нам необходимо из исходного числа $1$ получить число $23$, используя не более 5 команд. Доступные команды: 1 (умножить на 3) и 2 (вычесть 1).

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $23$ к исходному числу $1$. При этом действия команд меняются на противоположные: вместо «умножить на 3» мы будем «делить на 3» (если число делится без остатка), а вместо «вычесть 1» будем «прибавлять 1».

Шаг 1. Начнём с числа $23$. Оно не делится на 3, поэтому единственный возможный обратный ход — прибавить 1.
$23 + 1 = 24$. (Это соответствует прямой команде 2: $24 - 1 = 23$).

Шаг 2. Число $24$ делится на 3. Попробуем деление, так как оно быстрее уменьшает число.
$24 / 3 = 8$. (Это соответствует прямой команде 1: $8 \cdot 3 = 24$).

Шаг 3. Число $8$ не делится на 3. Прибавляем 1.
$8 + 1 = 9$. (Это соответствует прямой команде 2: $9 - 1 = 8$).

Шаг 4. Число $9$ делится на 3. Делим на 3.
$9 / 3 = 3$. (Это соответствует прямой команде 1: $3 \cdot 3 = 9$).

Шаг 5. Число $3$ делится на 3. Делим на 3.
$3 / 3 = 1$. (Это соответствует прямой команде 1: $1 \cdot 3 = 3$).

Мы пришли к исходному числу $1$ ровно за 5 шагов. Теперь запишем команды в прямом порядке (от $1$ к $23$):
1. $1 \cdot 3 = 3$ (команда 1)
2. $3 \cdot 3 = 9$ (команда 1)
3. $9 - 1 = 8$ (команда 2)
4. $8 \cdot 3 = 24$ (команда 1)
5. $24 - 1 = 23$ (команда 2)

Последовательность номеров команд: 11212.

Ответ: 11212

Источник: ФИПИ