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

Решение.

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

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

Попробуем восстановить путь от $49$ к $1$:

Шаг 1. Число $49$ не делится на $4$. Значит, на последнем этапе мы могли прийти к нему только вычитанием тройки. Применяем обратную операцию: $49 + 3 = 52$. (Команда 1)

Шаг 2. Число $52$ делится на $4$: $52 : 4 = 13$. Также можно было бы прибавить 3 ($52 + 3 = 55$), но деление быстрее приближает нас к единице. Проверим деление: $52 : 4 = 13$. (Команда 2)

Шаг 3. Число $13$ не делится на $4$. Применяем обратную операцию: $13 + 3 = 16$. (Команда 1)

Шаг 4. Число $16$ делится на $4$: $16 : 4 = 4$. (Команда 2)

Шаг 5. Число $4$ делится на $4$: $4 : 4 = 1$. Мы пришли к исходному числу! (Команда 2)

Теперь запишем команды в прямом порядке (от $1$ к $49$). Мы выполняли действия в обратном порядке: 1, 2, 1, 2, 2. Значит, прямой порядок будет зеркальным:
1. Команда 2: $1 \cdot 4 = 4$
2. Команда 2: $4 \cdot 4 = 16$
3. Команда 1: $16 - 3 = 13$
4. Команда 2: $13 \cdot 4 = 52$
5. Команда 1: $52 - 3 = 49$

Проверка: $1 \xrightarrow{2} 4 \xrightarrow{2} 16 \xrightarrow{1} 13 \xrightarrow{2} 52 \xrightarrow{1} 49$. Алгоритм состоит из 5 команд: 22121.

Ответ: 22121

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