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

Решение.

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

Будем рассуждать логически, двигаясь от начального числа $3$ к конечному числу $30$, перебирая возможные варианты команд на каждом шаге.

Шаг 1. У нас есть число $3$.
Если мы применим команду 1 ($3 - 3 = 0$), то из нуля умножением на $5$ мы не сможем получить положительное число $30$. Значит, первая команда должна быть №2.
Применяем команду 2: $3 \cdot 5 = 15$.
Промежуточный результат: 15. Алгоритм: 2.

Шаг 2. У нас есть число $15$.
Если мы снова умножим на $5$, то получим $75$. Это число значительно больше итогового ($30$), и нам придется многократно вычитать $3$, что может не уложиться в лимит 5 команд. Попробуем сначала вычесть $3$.
Применяем команду 1: $15 - 3 = 12$.
Промежуточный результат: 12. Алгоритм: 21.

Шаг 3. У нас есть число $12$.
Если мы умножим на $5$, получим $60$. Если вычтем $3$, получим $9$. Попробуем вычесть $3$.
Применяем команду 1: $12 - 3 = 9$.
Промежуточный результат: 9. Алгоритм: 211.

Шаг 4. У нас есть число $9$.
Попробуем снова вычесть $3$.
Применяем команду 1: $9 - 3 = 6$.
Промежуточный результат: 6. Алгоритм: 2111.

Шаг 5. У нас есть число $6$.
Нам нужно получить $30$. Заметим, что $6 \cdot 5 = 30$. Это в точности соответствует команде №2.
Применяем команду 2: $6 \cdot 5 = 30$.
Конечный результат: 30. Алгоритм: 21112.

Проверим полученную последовательность команд 21112:
1) $3 \cdot 5 = 15$ (команда 2)
2) $15 - 3 = 12$ (команда 1)
3) $12 - 3 = 9$ (команда 1)
4) $9 - 3 = 6$ (команда 1)
5) $6 \cdot 5 = 30$ (команда 2)
Алгоритм состоит из 5 команд и приводит к нужному числу.

Ответ: 21112

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