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

Решение.

Нам необходимо составить алгоритм для получения из числа $3$ числа $84$, используя не более $5$ команд. Доступны команды: 1 (прибавь $1$) и 2 (возведи в квадрат).

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

Попробуем восстановить путь от $84$ к $3$ за $5$ шагов:

Шаг 1. Число $84$ не является полным квадратом, поэтому мы не можем применить обратную команду 2 (извлечение корня). Применяем обратную команду 1:
$84 - 1 = 83$. (Команда 1)

Шаг 2. Число $83$ также не является квадратом. Снова применяем обратную команду 1:
$83 - 1 = 82$. (Команда 1)

Шаг 3. Число $82$ не является квадратом. Применяем обратную команду 1:
$82 - 1 = 81$. (Команда 1)

Шаг 4. Число $81$ является квадратом числа $9$. Применим обратную команду 2 (извлечение корня):
$\sqrt{81} = 9$. (Команда 2)

Шаг 5. Число $9$ является квадратом числа $3$. Применим обратную команду 2 (извлечение корня):
$\sqrt{9} = 3$. (Команда 2)

Мы пришли к исходному числу $3$ ровно за $5$ шагов. Теперь запишем команды в прямом порядке (от $3$ к $84$), заменяя обратные действия на исходные:

1. Возведи в квадрат: $3^{2} = 9$ (Команда 2)
2. Возведи в квадрат: $9^{2} = 81$ (Команда 2)
3. Прибавь 1: $81 + 1 = 82$ (Команда 1)
4. Прибавь 1: $82 + 1 = 83$ (Команда 1)
5. Прибавь 1: $83 + 1 = 84$ (Команда 1)

Последовательность команд: 22111.

Ответ: 22111

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