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

Решение.

Нам необходимо составить алгоритм для исполнителя «Вычислитель», который превращает число $1$ в число $23$ за ограниченное количество шагов (не более 5 команд). У нас есть две команды: 1 (умножить на 3) и 2 (вычесть 1).

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

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

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

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

Шаг 4. Число $9$ делится на $3$. Выполним деление.
$9 : 3 = 3$ (это команда 1 в прямом порядке).
Теперь у нас есть число $3$.

Шаг 5. Число $3$ делится на $3$. Выполним деление.
$3 : 3 = 1$ (это команда 1 в прямом порядке).
Мы пришли к исходному числу $1$.

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

Последовательность команд: 11212. Проверим количество: ровно 5 команд, что соответствует условию задачи.

Ответ: 11212

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