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

Решение.

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

Попробуем построить цепочку вычислений, анализируя возможные действия на каждом шаге. Поскольку нам нужно получить число $29$ из $9$ всего за $5$ команд, число должно расти достаточно быстро, а значит, мы будем часто использовать умножение.

Шаг 1. Начнём с числа $9$. Применим команду №2 (вычти 1):
$9 - 1 = 8$.
(Если бы мы сразу умножили на 2, получили бы 18, что тоже возможно, но проверим этот путь).

Шаг 2. К числу $8$ применим команду №1 (умножь на 2):
$8 \cdot 2 = 16$.

Шаг 3. К числу $16$ применим команду №2 (вычти 1):
$16 - 1 = 15$.

Шаг 4. К числу $15$ применим команду №1 (умножь на 2):
$15 \cdot 2 = 30$.

Шаг 5. К числу $30$ применим команду №2 (вычти 1):
$30 - 1 = 29$.

Проверим полученную последовательность команд: 2 (вычли 1), 1 (умножили на 2), 2 (вычли 1), 1 (умножили на 2), 2 (вычли 1).
Запишем вычисления в одну строку для проверки:
$((9 - 1) \cdot 2 - 1) \cdot 2 - 1 = (8 \cdot 2 - 1) \cdot 2 - 1 = (16 - 1) \cdot 2 - 1 = 15 \cdot 2 - 1 = 30 - 1 = 29$.
Алгоритм состоит из 5 команд, что соответствует условию задачи.

Номера команд по порядку: 2, 1, 2, 1, 2.

Ответ: 21212

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