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

Решение. Для решения этой задачи нам нужно найти последовательность из не более чем пяти команд, которая превращает число $3$ в число $66$. У нас есть две операции: вычитание $3$ (команда 1) и умножение на $5$ (команда 2).

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

Попробуем восстановить путь от $66$ к $3$ за 5 шагов:
Шаг 5: Число $66$. Оно не делится на $5$, значит, последней командой в прямом алгоритме была команда 1 (вычти 3). В обратном ходе прибавляем: $66 + 3 = 69$.
Шаг 4: Число $69$. Снова не делится на $5$. Применяем обратную команду 1: $69 + 3 = 72$.
Шаг 3: Число $72$. Не делится на $5$. Применяем обратную команду 1: $72 + 3 = 75$.
Шаг 2: Число $75$. Это число делится на $5$. Применяем обратную команду 2: $75 / 5 = 15$.
Шаг 1: Число $15$. Оно также делится на $5$. Применяем обратную команду 2: $15 / 5 = 3$.
Мы пришли к исходному числу $3$.

Теперь запишем команды в прямом порядке (от шага 1 к шагу 5):
1. Число $3$. Умножаем на $5$ (команда 2): $3 \cdot 5 = 15$.
2. Число $15$. Умножаем на $5$ (команда 2): $15 \cdot 5 = 75$.
3. Число $75$. Вычитаем $3$ (команда 1): $75 - 3 = 72$.
4. Число $72$. Вычитаем $3$ (команда 1): $72 - 3 = 69$.
5. Число $69$. Вычитаем $3$ (команда 1): $69 - 3 = 66$.

Последовательность команд: 2, 2, 1, 1, 1.

Ответ: 22111

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