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

Решение.

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

Попробуем рассуждать «от обратного» — из конечного числа $49$ прийти к начальному числу $4$. Это часто удобнее, так как возведение в квадрат заменяется извлечением корня, а вычитание — сложением.

Шаг 1. Последним действием мы могли получить $49$.
Вариант А: Командой «возведи в квадрат». Тогда предыдущее число было $\sqrt{49} = 7$.
Вариант Б: Командой «вычти 3». Тогда предыдущее число было $49 + 3 = 52$.
Число $52$ не является квадратом и оно больше исходного, поэтому вариант А ($7 \rightarrow 49$) выглядит перспективнее.

Шаг 2. Как получить число $7$?
Вариант А: Командой «возведи в квадрат». Но $\sqrt{7}$ не является натуральным числом, а исполнитель работает только с натуральными числами.
Вариант Б: Командой «вычти 3». Тогда предыдущее число было $7 + 3 = 10$.

Шаг 3. Как получить число $10$?
Вариант А: Командой «возведи в квадрат». $\sqrt{10}$ — не натуральное.
Вариант Б: Командой «вычти 3». Тогда предыдущее число было $10 + 3 = 13$.

Шаг 4. Как получить число $13$?
Вариант А: Командой «возведи в квадрат». $\sqrt{13}$ — не натуральное.
Вариант Б: Командой «вычти 3». Тогда предыдущее число было $13 + 3 = 16$.

Шаг 5. Как получить число $16$?
Вариант А: Командой «возведи в квадрат». Тогда предыдущее число было $\sqrt{16} = 4$.
Это наше исходное число! Мы нашли путь за 5 шагов.

Теперь запишем команды в прямом порядке (от $4$ к $49$):
1. Число $4$. Возводим в квадрат (команда 2): $4^2 = 16$.
2. Число $16$. Вычитаем 3 (команда 1): $16 - 3 = 13$.
3. Число $13$. Вычитаем 3 (команда 1): $13 - 3 = 10$.
4. Число $10$. Вычитаем 3 (команда 1): $10 - 3 = 7$.
5. Число $7$. Возводим в квадрат (команда 2): $7^2 = 49$.

Последовательность команд: 2, 1, 1, 1, 2.

Ответ: 21112

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