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

Решение.

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

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

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

Шаг 2. Число $22$ не делится на $3$. Значит, на предыдущем шаге мы могли получить его только прибавлением тройки. Применим обратную команду 1 (вычитание $3$):
$22 - 3 = 19$. (Это команда 1).

Шаг 3. Число $19$ не делится на $3$. Снова применяем обратную команду 1:
$19 - 3 = 16$. (Это команда 1).

Шаг 4. Число $16$ не делится на $3$. Применяем обратную команду 1:
$16 - 3 = 13$.
Заметим: если мы продолжим вычитать по $3$, мы получим последовательность $13 \rightarrow 10 \rightarrow 7 \rightarrow 4 \rightarrow 1$. Это потребует слишком много команд (всего получится 8 команд, а по условию нужно не более 5). Значит, на шаге 2 или 3 нужно было действовать иначе.

Попробуем другой путь с конца:
1) $66 - 3 = 63$ (команда 1)
2) $63 : 3 = 21$ (команда 2)
3) $21 : 3 = 7$ (команда 2)
4) $7 - 3 = 4$ (команда 1)
5) $4 - 3 = 1$ (команда 1)

Мы пришли к числу $1$ ровно за 5 шагов. Теперь запишем эти команды в прямом порядке (от $1$ к $66$):
1. Начнём с $1$. Прибавим $3$ (команда 1): $1 + 3 = 4$.
2. Прибавим $3$ (команда 1): $4 + 3 = 7$.
3. Умножим на $3$ (команда 2): $7 \cdot 3 = 21$.
4. Умножим на $3$ (команда 2): $21 \cdot 3 = 63$.
5. Прибавим $3$ (команда 1): $63 + 3 = 66$.

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

Ответ: 11221

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