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

Решение.

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

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

Шаг 1. Рассмотрим число $72$. Оно делится на $3$. Попробуем применить деление (обратная команда 2):
$72 : 3 = 24$. (Это была бы команда 2, если идти от $1$ к $72$).

Шаг 2. Рассмотрим число $24$. Оно также делится на $3$. Снова применим деление (обратная команда 2):
$24 : 3 = 8$. (Это еще одна команда 2).

Шаг 3. Число $8$ не делится на $3$. Значит, мы можем только вычитать (обратная команда 1):
$8 - 3 = 5$. (Это команда 1).

Шаг 4. Число $5$ не делится на $3$. Снова вычитаем (обратная команда 1):
$5 - 3 = 2$. (Это команда 1).

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

Попробуем другой путь. На шаге 2 вместо деления попробуем вычитание:
1) $72 : 3 = 24$ (команда 2)
2) $24 - 3 = 21$ (команда 1)
3) $21 : 3 = 7$ (команда 2)
4) $7 - 3 = 4$ (команда 1)
5) $4 - 3 = 1$ (команда 1)

Мы получили число $1$ ровно за 5 шагов. Теперь запишем эти команды в прямом порядке (от $1$ к $72$):
1. (Начало) Число $1$
2. Прибавь $3$ (команда 1): $1 + 3 = 4$
3. Прибавь $3$ (команда 1): $4 + 3 = 7$
4. Умножь на $3$ (команда 2): $7 \cdot 3 = 21$
5. Прибавь $3$ (команда 1): $21 + 3 = 24$
6. Умножь на $3$ (команда 2): $24 \cdot 3 = 72$

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

Ответ: 11212

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