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

Решение.

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

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

Шаг 1. Последнее число — $57$. Проверим, делится ли оно на $3$.
$57 : 3 = 19$. Число делится нацело, значит, последней командой могло быть умножение (команда 2).
Если же мы вычтем $3$, получим: $57 - 3 = 54$.
Попробуем идти через деление: $57 \xrightarrow{/3} 19$. Это была команда 2.

Шаг 2. Теперь у нас число $19$. Оно не делится на $3$, поэтому единственный вариант — вычесть $3$.
$19 - 3 = 16$. Это была команда 1.

Шаг 3. Число $16$. Оно не делится на $3$, снова вычитаем $3$.
$16 - 3 = 13$. Это была команда 1.

Шаг 4. Число $13$. Оно не делится на $3$, вычитаем $3$.
$13 - 3 = 10$. Это была команда 1. (Замечаем, что мы отдаляемся от единицы слишком медленно, попробуем другой путь).

Вернемся к Шагу 1 и попробуем вычитание:
1) $57 - 3 = 54$ (команда 1).
2) $54$ делится на $3$: $54 : 3 = 18$ (команда 2).
3) $18$ делится на $3$: $18 : 3 = 6$ (команда 2).
4) $6$ делится на $3$: $6 : 3 = 2$ (команда 2). Но нам нужно прийти к $1$.
Попробуем на 4-м шаге вычесть: $18 - 3 = 15$ (команда 1).
5) $15 : 3 = 5$ или $15 - 3 = 12$. Снова не получается $1$ за 5 шагов.

Попробуем еще раз, комбинируя команды:
1) $57 : 3 = 19$ (команда 2)
2) $19 - 3 = 16$ (команда 1) — не подходит.
Попробуем так:
1) $57 - 3 = 54$ (команда 1)
2) $54 : 3 = 18$ (команда 2)
3) $18 : 3 = 6$ (команда 2)
4) $6 : 3 = 2$ (команда 2)
5) $2$ — не подходит.

Правильный путь (проверка варианта 21221):
1) Начнем с $1$. Применим команду 2 (умножь на 3): $1 \cdot 3 = 3$.
2) Применим команду 1 (прибавь 3): $3 + 3 = 6$.
3) Применим команду 2 (умножь на 3): $6 \cdot 3 = 18$.
4) Применим команду 2 (умножь на 3): $18 \cdot 3 = 54$.
5) Применим команду 1 (прибавь 3): $54 + 3 = 57$.
Всего $5$ команд. Последовательность номеров: $2, 1, 2, 2, 1$.

Ответ: 21221

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