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

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

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

Попробуем восстановить путь от $21$ к $3$ за 5 шагов:
Шаг 1: Число $21$ не делится на 2, поэтому единственный вариант — прибавить 1. $21 + 1 = 22$ (соответствует обратной команде 1).
Шаг 2: Число $22$ четное, его выгодно разделить на 2. $22 / 2 = 11$ (соответствует обратной команде 2).
Шаг 3: Число $11$ нечетное, прибавляем 1. $11 + 1 = 12$ (соответствует обратной команде 1).
Шаг 4: Число $12$ четное, делим на 2. $12 / 2 = 6$ (соответствует обратной команде 2).
Шаг 5: Число $6$ четное, делим на 2. $6 / 2 = 3$ (соответствует обратной команде 2). Мы пришли к исходному числу $3$ ровно за 5 шагов.

Теперь запишем эти действия в прямом порядке (от $3$ к $21$), заменяя обратные действия на исходные команды:
1. Число $3$, команда 2 (умножь на 2): $3 \cdot 2 = 6$
2. Число $6$, команда 2 (умножь на 2): $6 \cdot 2 = 12$
3. Число $12$, команда 1 (вычти 1): $12 - 1 = 11$
4. Число $11$, команда 2 (умножь на 2): $11 \cdot 2 = 22$
5. Число $22$, команда 1 (вычти 1): $22 - 1 = 21$

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

Ответ: 22121

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