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

Решение.

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

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

Шаг 1. Последнее число — $60$. Оно делится на $3$. Попробуем обратную команду «раздели на 3»: $60 : 3 = 20$. Это соответствует прямой команде №1. Если бы мы вычли $1$, получили бы $59$, что дальше от цели.
Текущий путь (с конца): $60 \leftarrow 20$ (команда 1).

Шаг 2. Число $20$. Оно не делится на $3$. Значит, единственный вариант — вычесть $1$: $20 - 1 = 19$.
Текущий путь (с конца): $60 \leftarrow 20 \leftarrow 19$ (команда 2).

Шаг 3. Число $19$. Оно не делится на $3$. Вычитаем $1$: $19 - 1 = 18$.
Текущий путь (с конца): $60 \leftarrow 20 \leftarrow 19 \leftarrow 18$ (команда 2).

Шаг 4. Число $18$. Оно делится на $3$: $18 : 3 = 6$.
Текущий путь (с конца): $60 \leftarrow 20 \leftarrow 19 \leftarrow 18 \leftarrow 6$ (команда 1).

Шаг 5. Число $6$. Чтобы получить из $5$ число $6$, нужно прибавить $1$: $6 - 1 = 5$.
Текущий путь (с конца): $60 \leftarrow 20 \leftarrow 19 \leftarrow 18 \leftarrow 6 \leftarrow 5$ (команда 2).

Теперь запишем команды в прямом порядке (от $5$ к $60$):
1) $5 + 1 = 6$ (команда 2)
2) $6 \cdot 3 = 18$ (команда 1)
3) $18 + 1 = 19$ (команда 2)
4) $19 + 1 = 20$ (команда 2)
5) $20 \cdot 3 = 60$ (команда 1)

Полученная последовательность команд: 21221. Она содержит ровно $5$ команд, что соответствует условию задачи.

Ответ: 21221

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