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

Решение.

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

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

Шаг 1. Начнём с числа $44$. Оно чётное, поэтому его можно разделить на $2$. $44 : 2 = 22$ (команда 2 в обратном порядке). Если бы мы вычли $2$, получили бы $42$, что тоже возможно, но деление быстрее уменьшает число.

Шаг 2. Теперь у нас число $22$. Оно также чётное, разделим его на $2$. $22 : 2 = 11$ (команда 2 в обратном порядке).

Шаг 3. Число $11$ нечётное, на $2$ не делится. Единственный вариант — вычесть $2$. $11 - 2 = 9$ (команда 1 в обратном порядке).

Шаг 4. Число $9$ нечётное, вычитаем $2$. $9 - 2 = 7$ (команда 1 в обратном порядке).

Шаг 5. Число $7$ нечётное, вычитаем $2$. $7 - 2 = 5$ (команда 1 в обратном порядке). Мы не пришли к числу $3$ за 5 шагов. Значит, нужно изменить стратегию на предыдущих этапах.

Попробуем другой путь: 1) $44 : 2 = 22$ (обратная команде 2) 2) $22 : 2 = 11$ (обратная команде 2) 3) $11 - 2 = 9$ (обратная команде 1) Стоп, если мы на шаге 2 вычтем $2$ вместо деления? 1) $44 : 2 = 22$ (обратная команде 2) 2) $22 - 2 = 20$ (обратная команде 1) 3) $20 : 2 = 10$ (обратная команде 2) 4) $10 : 2 = 5$ — не подходит. Попробуем: 1) $44 : 2 = 22$ (обратная команде 2) 2) $22 - 2 = 20$ (обратная команде 1) 3) $20 - 2 = 18$ (обратная команде 1) 4) $18 : 2 = 9$ — не подходит.

Вернёмся к прямой последовательности команд, проверяя ответ 12212: 1. Команда 1: $3 + 2 = 5$ 2. Команда 2: $5 \cdot 2 = 10$ 3. Команда 2: $10 \cdot 2 = 20$ 4. Команда 1: $20 + 2 = 22$ 5. Команда 2: $22 \cdot 2 = 44$

Проверим количество команд: их ровно $5$. Результат совпадает с требуемым числом $44$. Последовательность номеров команд: $1, 2, 2, 1, 2$.

Ответ: 12212

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