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

Решение.

Разберём, как работают команды исполнителя:
1. Команда 1: $x - 3$ (вычитание трёх).
2. Команда 2: $x \cdot 10 + 1$ (приписывание единицы справа превращает число $x$ в $x1$).

Нам нужно из числа $8$ получить число $15$ не более чем за 5 шагов. Попробуем действовать методом подбора, анализируя возможности применения команд.

Шаг 1. Если мы применим команду 1 к числу $8$, получим $5$. Если применим команду 2, получим $81$. Число $81$ намного больше итогового ($15$), но из него можно вычитать по 3. Однако за оставшиеся 4 команды мы не успеем уменьшить $81$ до $15$, так как $81 - 3 \cdot 4 = 69$.
Значит, первая команда — 1.
Число: $8 - 3 = 5$.

Шаг 2. К числу $5$ применим команду 1. Получим $2$. (Если применить команду 2, получим $51$, что опять слишком велико для 5 шагов).
Значит, вторая команда — 1.
Число: $5 - 3 = 2$.

Шаг 3. Теперь у нас есть число $2$. Чтобы получить число, заканчивающееся на $5$ или близкое к нему, выгодно использовать команду 2 (приписать 1).
Применим команду 2: к числу $2$ приписываем $1$, получаем $21$.
Значит, третья команда — 2.
Число: $21$.

Шаг 4. Нам нужно из $21$ получить $15$. Разность составляет $21 - 15 = 6$. Число $6$ делится на $3$ ровно два раза. Это идеально подходит под оставшееся количество команд.
Применим команду 1: $21 - 3 = 18$.
Значит, четвёртая команда — 1.

Шаг 5. Применим команду 1 ещё раз: $18 - 3 = 15$.
Цель достигнута за 5 команд.
Значит, пятая команда — 1.

Проверим последовательность команд 11211:
1) $8 - 3 = 5$
2) $5 - 3 = 2$
3) $2 \rightarrow 21$
4) $21 - 3 = 18$
5) $18 - 3 = 15$

Алгоритм верный.

Ответ: 11211

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