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

Решение.

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

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

Шаг 1. Начнём с числа $42$. Оно не делится на $5$, поэтому мы можем только прибавить $3$:
$42 + 3 = 45$. (Это была обратная команда 1, значит, последняя команда в прямом алгоритме — 1).

Шаг 2. Число $45$ делится на $5$. Попробуем деление, так как оно быстрее уменьшает число:
$45 / 5 = 9$. (Это была обратная команда 2, значит, предпоследняя команда в прямом алгоритме — 2).

Шаг 3. Число $9$ не делится на $5$, прибавляем $3$:
$9 + 3 = 12$. (Обратная команда 1, в прямом алгоритме — 1).

Шаг 4. Число $12$ не делится на $5$, прибавляем $3$:
$12 + 3 = 15$. (Обратная команда 1, в прямом алгоритме — 1).

Шаг 5. Число $15$ делится на $5$. Пробуем деление:
$15 / 5 = 3$. (Обратная команда 2, в прямом алгоритме — 2).
Мы пришли к исходному числу $3$. Всего затрачено $5$ действий.

Теперь запишем команды в прямом порядке (от шага 5 к шагу 1):
1. (Команда 2): $3 \cdot 5 = 15$
2. (Команда 1): $15 - 3 = 12$
3. (Команда 1): $12 - 3 = 9$
4. (Команда 2): $9 \cdot 5 = 45$
5. (Команда 1): $45 - 3 = 42$

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

Ответ: 21121

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