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

Решение.

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

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

Шаг 1. Последнее число — $48$. Можно ли его разделить на $3$? Да, $48 : 3 = 16$. Но если мы получим $16$, то на следующем шаге (двигаясь назад) мы не сможем ни разделить $16$ на $3$, ни быстро прийти к единице. Попробуем другой вариант: вычтем $3$.
$48 - 3 = 45$. (Это была бы команда 1, если идти вперед).

Шаг 2. Число $45$. Оно отлично делится на $3$:
$45 : 3 = 15$. (Это команда 2).

Шаг 3. Число $15$. Снова пробуем деление на $3$:
$15 : 3 = 5$. (Это команда 2).

Шаг 4. Число $5$. На $3$ оно не делится, значит, остается только вычитание:
$5 - 3 = 2$. (Это команда 1). Но из $2$ мы не получим $1$ за один шаг. Значит, этот путь не совсем верный. Вернемся к шагу 3.

Попробуем другой путь (перебор вариантов):
1) Начнем с начала: $1$.
2) Команда 1: $1 + 3 = 4$.
3) Команда 2: $4 \cdot 3 = 12$.
4) Команда 1: $12 + 3 = 15$.
5) Команда 2: $15 \cdot 3 = 45$.
6) Команда 1: $45 + 3 = 48$.

Проверим количество команд и результат:
1. $1 + 3 = 4$ (команда 1)
2. $4 \cdot 3 = 12$ (команда 2)
3. $12 + 3 = 15$ (команда 1)
4. $15 \cdot 3 = 45$ (команда 2)
5. $45 + 3 = 48$ (команда 1)

Алгоритм состоит из 5 команд: 1, 2, 1, 2, 1. Это соответствует условию задачи (не более 5 команд).

Ответ: 12121

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