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

Решение.

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

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

Шаг 1. Начнём с числа $84$.
Число $84$ делится на $3$ ($84 : 3 = 28$). Это выгодная операция, так как она быстрее уменьшает число.
Применим обратную команду №1: $84 : 3 = 28$. (Это была команда 1 в прямом порядке).

Шаг 2. Теперь у нас число $28$.
Число $28$ не делится на $3$. Значит, единственный вариант — вычесть $1$.
Применим обратную команду №2: $28 - 1 = 27$. (Это была команда 2 в прямом порядке).

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

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

Шаг 5. Теперь у нас число $3$.
Нам нужно получить число $2$. Если мы разделим на $3$, получим $1$, что нам не подходит. Поэтому вычтем $1$.
Применим обратную команду №2: $3 - 1 = 2$. (Это была команда 2 в прямом порядке).

Мы пришли к исходному числу $2$. Теперь запишем команды в прямом порядке (от числа $2$ к числу $84$), учитывая, что мы восстанавливали их с конца:
1. Сначала мы сделали $2 + 1 = 3$ (команда 2).
2. Затем $3 \cdot 3 = 9$ (команда 1).
3. Затем $9 \cdot 3 = 27$ (команда 1).
4. Затем $27 + 1 = 28$ (команда 2).
5. И наконец $28 \cdot 3 = 84$ (команда 1).

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

Ответ: 21121

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