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

Решение.

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

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

Попробуем восстановить путь от $88$ к $4$ за 5 шагов:

Шаг 1. Число $88$ не делится на $5$. Значит, единственная возможная обратная операция — прибавление $4$.
$88 + 4 = 92$
(Это соответствует команде 1 в прямом порядке).

Шаг 2. Число $92$ не делится на $5$. Снова прибавляем $4$.
$92 + 4 = 96$
(Это соответствует команде 1 в прямом порядке).

Шаг 3. Число $96$ не делится на $5$. Снова прибавляем $4$.
$96 + 4 = 100$
(Это соответствует команде 1 в прямом порядке).

Шаг 4. Число $100$ делится на $5$. Попробуем выполнить деление, так как это быстрее приведет нас к маленькому числу $4$.
$100 : 5 = 20$
(Это соответствует команде 2 в прямом порядке).

Шаг 5. Число $20$ делится на $5$. Снова делим на $5$.
$20 : 5 = 4$
(Это соответствует команде 2 в прямом порядке).

Мы пришли к исходному числу $4$. Теперь запишем команды в прямом порядке (от $4$ к $88$):
1. $4 \cdot 5 = 20$ (команда 2)
2. $20 \cdot 5 = 100$ (команда 2)
3. $100 - 4 = 96$ (команда 1)
4. $96 - 4 = 92$ (команда 1)
5. $92 - 4 = 88$ (команда 1)

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

Ответ: 22111

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