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

Решение.

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

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

Попробуем восстановить путь от $18$ к $3$ за 5 шагов:

1. Число $18$ четное, поэтому выгодно применить обратное действие деления: $18 : 2 = 9$. (Это соответствует команде 2 в прямом порядке).
2. Число $9$ нечетное, делить на 2 нельзя. Применяем обратное действие сложения: $9 + 1 = 10$. (Это соответствует команде 1 в прямом порядке).
3. Число $10$ четное, делим на 2: $10 : 2 = 5$. (Это соответствует команде 2 в прямом порядке).
4. Число $5$ нечетное, прибавляем 1: $5 + 1 = 6$. (Это соответствует команде 1 в прямом порядке).
5. Число $6$ четное, делим на 2: $6 : 2 = 3$. (Это соответствует команде 2 в прямом порядке).

Мы пришли к исходному числу $3$ ровно за 5 шагов. Теперь запишем команды в прямом порядке (от $3$ к $18$), учитывая, что мы шли с конца:

Шаг 1 (из $3$ в $6$): умножь на 2 — команда 2
Шаг 2 (из $6$ в $5$): вычти 1 — команда 1
Шаг 3 (из $5$ в $10$): умножь на 2 — команда 2
Шаг 4 (из $10$ в $9$): вычти 1 — команда 1
Шаг 5 (из $9$ в $18$): умножь на 2 — команда 2

Проверим полученную последовательность $21212$:
$3 \cdot 2 = 6$
$6 - 1 = 5$
$5 \cdot 2 = 10$
$10 - 1 = 9$
$9 \cdot 2 = 18$
Алгоритм верный и содержит 5 команд.

Ответ: 21212

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