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

Решение.

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

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

Шаг 1. Начнём с исходного числа $5$.
Если мы применим команду 1: $5 \cdot 3 = 15$.
Если мы применим команду 2: $5 - 4 = 1$.
Попробуем пойти по пути первого варианта, так как $15$ ближе к цели ($17$).

Шаг 2. У нас есть число $15$.
Если мы применим команду 1: $15 \cdot 3 = 45$ (это слишком много, нам нужно всего $17$).
Применим команду 2: $15 - 4 = 11$.
Запишем последовательность: $5 \xrightarrow{1} 15 \xrightarrow{2} 11$.

Шаг 3. У нас есть число $11$.
Если мы применим команду 1: $11 \cdot 3 = 33$ (всё ещё много).
Применим команду 2: $11 - 4 = 7$.
Запишем последовательность: $5 \xrightarrow{1} 15 \xrightarrow{2} 11 \xrightarrow{2} 7$.

Шаг 4. У нас есть число $7$.
Попробуем применить команду 1: $7 \cdot 3 = 21$.
Это число больше искомого ($17$), но оно удобно тем, что разница между $21$ и $17$ составляет ровно $4$, что соответствует нашей второй команде.
Запишем последовательность: $5 \xrightarrow{1} 15 \xrightarrow{2} 11 \xrightarrow{2} 7 \xrightarrow{1} 21$.

Шаг 5. У нас есть число $21$.
Применим команду 2: $21 - 4 = 17$.
Мы получили искомое число $17$ ровно за 5 команд.

Проверим итоговую последовательность команд 12212:
1) $5 \cdot 3 = 15$
2) $15 - 4 = 11$
3) $11 - 4 = 7$
4) $7 \cdot 3 = 21$
5) $21 - 4 = 17$

Алгоритм верный и содержит 5 команд.

Ответ: 12212

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