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

Решение.

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

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

Шаг 1. Начнём с числа $26$.
Число $26$ не делится на $3$, поэтому мы можем только прибавить $1$:
$26 + 1 = 27$. (Команда №1 в обратном порядке)

Шаг 2. Теперь у нас число $27$.
Число $27$ делится на $3$. Попробуем деление, так как оно быстрее приближает нас к числу $5$:
$27 : 3 = 9$. (Команда №2 в обратном порядке)

Шаг 3. Теперь у нас число $9$.
Число $9$ делится на $3$. Снова используем деление:
$9 : 3 = 3$. (Команда №2 в обратном порядке)

Шаг 4. Теперь у нас число $3$.
Нам нужно получить $5$. Если мы продолжим делить, получим $1$, что далеко от цели. Попробуем прибавлять единицы:
$3 + 1 = 4$. (Команда №1 в обратном порядке)

Шаг 5. Теперь у нас число $4$.
Прибавим ещё одну единицу:
$4 + 1 = 5$. (Команда №1 в обратном порядке)

Мы пришли к исходному числу $5$ за 5 шагов. Теперь запишем команды в прямом порядке (от $5$ к $26$), заменяя обратные действия на исходные:
1. Число $5$: вычтем 1 (команда 1) $\rightarrow 4$
2. Число $4$: вычтем 1 (команда 1) $\rightarrow 3$
3. Число $3$: умножим на 3 (команда 2) $\rightarrow 9$
4. Число $9$: умножим на 3 (команда 2) $\rightarrow 27$
5. Число $27$: вычтем 1 (команда 1) $\rightarrow 26$

Проверим последовательность команд: $11221$.
$5 - 1 = 4$
$4 - 1 = 3$
$3 \cdot 3 = 9$
$9 \cdot 3 = 27$
$27 - 1 = 26$

Алгоритм состоит из 5 команд и приводит к верному результату.

Ответ: 11221

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