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

Решение.

Нам необходимо составить алгоритм для исполнителя «Вычислитель», который превращает число $1$ в число $25$ ровно за $5$ шагов (команд). У нас есть две команды: прибавление $3$ (команда 1) и умножение на $2$ (команда 2).

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

Шаг 1. Последнее число — $25$. Оно не делится на $2$ без остатка, значит, последней командой не могло быть умножение. Следовательно, на последнем шаге прибавили $3$.
Выполняем обратное действие: $25 - 3 = 22$. (Команда 1)

Шаг 2. Теперь у нас число $22$. Оно делится на $2$. Попробуем деление: $22 : 2 = 11$. (Команда 2)

Шаг 3. Число $11$. Оно не делится на $2$. Значит, вычитаем $3$:
$11 - 3 = 8$. (Команда 1)

Шаг 4. Число $8$. Оно делится на $2$. Попробуем деление: $8 : 2 = 4$. (Команда 2)

Шаг 5. Число $4$. Нам нужно получить исходную единицу за один шаг.
Вычитаем $3$: $4 - 3 = 1$. (Команда 1)

Мы пришли к числу $1$ ровно за $5$ шагов. Теперь запишем команды в прямом порядке (от первого шага к последнему):
1. Число $1$, команда 1: $1 + 3 = 4$
2. Число $4$, команда 2: $4 \cdot 2 = 8$
3. Число $8$, команда 1: $8 + 3 = 11$
4. Число $11$, команда 2: $11 \cdot 2 = 22$
5. Число $22$, команда 1: $22 + 3 = 25$

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

Ответ: 12121

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