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

Решение.

Нам необходимо составить алгоритм для исполнителя Квадратор, который преобразует число $5$ в число $80$ за не более чем $5$ шагов. У исполнителя есть две команды: 1) вычти $1$; 2) возведи в квадрат.

Для решения таких задач удобнее идти от конечного результата к начальному числу, используя обратные операции. Обратной операцией для вычитания $1$ является прибавление $1$, а для возведения в квадрат — извлечение квадратного корня.

Попробуем восстановить путь от $80$ к $5$:

Шаг 1. Число $80$ не является полным квадратом, поэтому мы не можем применить обратную команду "извлеки корень". Значит, на последнем шаге была выполнена прямая команда 1 (вычти $1$).
Выполняем обратное действие: $80 + 1 = 81$. (Команда 1)

Шаг 2. Число $81$ является полным квадратом ($9^2 = 81$). Выгодно применить обратную команду "извлеки корень", так как это значительно уменьшает число и приближает нас к $5$.
Выполняем обратное действие: $\sqrt{81} = 9$. (Команда 2)

Шаг 3. Число $9$ также является полным квадратом ($3^2 = 9$). Однако, если мы извлечем корень, то получим $3$, что уже меньше нашего начального числа $5$. Нам нужно получить $5$, поэтому попробуем использовать обратное действие для вычитания.
Выполняем обратное действие: $9 + 1 = 10$. (Команда 1)

Шаг 4. Число $10$ не является квадратом.
Выполняем обратное действие: $10 + 1 = 11$. (Команда 1)

Шаг 5. Проверим, можем ли мы прийти к числу $5$ за оставшиеся шаги. Если мы прибавим еще единицу, получим $11 + 1 = 12$, что не ведет к $5$.
Вернемся к Шагу 3 и попробуем другой путь. Нам нужно получить $81$ из $5$ за $4$ команды.
1) $5 - 1 = 4$ (Команда 1)
2) $4 - 1 = 3$ (Команда 1)
3) $3^2 = 9$ (Команда 2)
4) $9^2 = 81$ (Команда 2)
5) $81 - 1 = 80$ (Команда 1)

Проверим полученную последовательность команд $11221$:
1. Число $5$, команда 1: $5 - 1 = 4$
2. Число $4$, команда 1: $4 - 1 = 3$
3. Число $3$, команда 2: $3^2 = 9$
4. Число $9$, команда 2: $9^2 = 81$
5. Число $81$, команда 1: $81 - 1 = 80$

Алгоритм $11221$ за $5$ команд превращает $5$ в $80$.

Ответ: 11221

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