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

Решение.

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

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

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

Шаг 2. Число $28$ не делится на $3$ нацело. Значит, на этом этапе мы могли использовать только обратную команду 1 (вычитание):
$28 - 3 = 25$. (Команда 1).

Шаг 3. Число $25$ не делится на $3$. Снова используем обратную команду 1:
$25 - 3 = 22$. (Команда 1).

Этот путь кажется длинным. Давайте попробуем другой вариант на Шаге 1 — использовать вычитание сразу.

Попробуем еще раз (двигаемся от 84 к 1):
1) $84 : 3 = 28$ (команда 2 в прямом порядке)
2) $28 : 3$ — не делится. Вычитаем: $28 - 3 = 25$.
Этот путь не ведет к быстрому результату. Попробуем сначала вычитать из $84$.

Правильный путь (от 1 к 84):
Проверим последовательность команд 22221, указанную в условии как верную:
1) Команда 2: $1 \cdot 3 = 3$
2) Команда 2: $3 \cdot 3 = 9$
3) Команда 2: $9 \cdot 3 = 27$
4) Команда 2: $27 \cdot 3 = 81$
5) Команда 1: $81 + 3 = 84$

Проверим количество команд: использовано ровно 5 команд. Все действия выполнены верно, итоговое число $84$ получено из числа $1$.

Запишем номера команд по порядку: 2 (умножь), 2 (умножь), 2 (умножь), 2 (умножь), 1 (прибавь).

Ответ: 22221

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