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

Решение.

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

Для решения таких задач удобнее идти от обратного: от конечного числа $177$ к начальному числу $7$. При этом команды заменяются на противоположные:
1. Вместо "вычти 3" будем выполнять "прибавь 3".
2. Вместо "умножь на 3" будем выполнять "раздели на 3".

Шаг 1. Попробуем применить обратную команду 2 к числу $177$. Число $177$ делится на $3$ (сумма цифр $1+7+7=15$, а $15$ делится на $3$).
$177 : 3 = 59$. (Это была обратная команда 2).

Шаг 2. Теперь работаем с числом $59$. Оно не делится на $3$. Значит, мы можем применить только обратную команду 1 (прибавь 3).
$59 + 3 = 62$. (Это была обратная команда 1).

Шаг 3. Число $62$ не делится на $3$. Снова применяем обратную команду 1.
$62 + 3 = 65$. (Это была обратная команда 1).

Видим, что мы отдаляемся от цели. Попробуем другой путь на Шаге 2. Если мы прибавим $3$ несколько раз, сможем ли мы получить число, делящееся на $3$?
Вернемся к числу $59$:
$59 + 3 = 62$ (не делится на 3)
$62 + 3 = 65$ (не делится на 3)
Этот путь кажется длинным. Давайте пересмотрим Шаг 1.

Попробуем еще раз с конца:
1) $177 : 3 = 59$ (команда 2 в обратном порядке)
2) $59 + 3 = 62$ (команда 1 в обратном порядке)
3) $62 + 3 = 65$
Этот путь не ведет к $7$ за нужное количество шагов. Попробуем применить команду 1 к числу $177$ сразу? Нет, число слишком большое.

Рассмотрим прямой ход (от 7 к 177):
1) $7 \cdot 3 = 21$ (команда 2)
2) $21 \cdot 3 = 63$ (команда 2)
3) $63 - 3 = 60$ (команда 1)
4) $60 \cdot 3 = 180$ (команда 2)
5) $180 - 3 = 177$ (команда 1)
Проверим количество команд: $2, 2, 1, 2, 1$ — всего 5 команд.

Проверка алгоритма 22121:
1. $7 \cdot 3 = 21$
2. $21 \cdot 3 = 63$
3. $63 - 3 = 60$
4. $60 \cdot 3 = 180$
5. $180 - 3 = 177$
Алгоритм верный и содержит ровно 5 команд.

Ответ: 22121

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