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

Решение.

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

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

Шаг 1. Начнём с числа $50$. Оно не делится на $4$ без остатка, поэтому мы можем применить только обратную команду №2 (вычитание):
$50 - 3 = 47$. (Команда в прямом порядке — №2)

Шаг 2. Число $47$ также не делится на $4$. Снова применяем вычитание:
$47 - 3 = 44$. (Команда в прямом порядке — №2)

Шаг 3. Число $44$ делится на $4$. Попробуем деление, так как оно быстрее уменьшает число:
$44 : 4 = 11$. (Команда в прямом порядке — №1)

Шаг 4. Число $11$ не делится на $4$. Применяем вычитание:
$11 - 3 = 8$. (Команда в прямом порядке — №2)

Шаг 5. Число $8$ делится на $4$. Пробуем деление:
$8 : 4 = 2$. (Команда в прямом порядке — №1)

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

1. Число $2$, команда №1 (умножь на $4$): $2 \cdot 4 = 8$;
2. Число $8$, команда №2 (прибавь $3$): $8 + 3 = 11$;
3. Число $11$, команда №1 (умножь на $4$): $11 \cdot 4 = 44$;
4. Число $44$, команда №2 (прибавь $3$): $44 + 3 = 47$;
5. Число $47$, команда №2 (прибавь $3$): $47 + 3 = 50$.

Последовательность номеров команд: $12122$.

Ответ: 12122

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