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

Решение.

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

Поскольку нам нужно получить число $30$, а возведение в квадрат очень быстро увеличивает числа, попробуем проанализировать возможные пути с конца (от $30$ к $3$), используя обратные операции: извлечение корня и прибавление $3$.

1. Рассмотрим конечное число $30$. Оно не является полным квадратом, значит, последней командой не могло быть возведение в квадрат. Следовательно, последней была команда 2 (вычти $3$).
До выполнения этой команды было число: $30 + 3 = 33$.
Алгоритм: $... \rightarrow 33 \xrightarrow{2} 30$.

2. Число $33$ также не является полным квадратом. Значит, перед ним снова была команда 2.
До выполнения этой команды было число: $33 + 3 = 36$.
Алгоритм: $... \rightarrow 36 \xrightarrow{2} 33 \xrightarrow{2} 30$.

3. Число $36$ является полным квадратом ($6^2$). Значит, оно могло быть получено командой 1 из числа $6$.
Алгоритм: $... \rightarrow 6 \xrightarrow{1} 36 \xrightarrow{2} 33 \xrightarrow{2} 30$.

4. Число $6$ не является полным квадратом. Значит, перед ним была команда 2.
До выполнения этой команды было число: $6 + 3 = 9$.
Алгоритм: $... \rightarrow 9 \xrightarrow{2} 6 \xrightarrow{1} 36 \xrightarrow{2} 33 \xrightarrow{2} 30$.

5. Число $9$ является полным квадратом ($3^2$). Оно могло быть получено командой 1 из нашего исходного числа $3$.
Алгоритм: $3 \xrightarrow{1} 9 \xrightarrow{2} 6 \xrightarrow{1} 36 \xrightarrow{2} 33 \xrightarrow{2} 30$.

Проверим полученную последовательность команд (12122) в прямом порядке:
1) Команда 1: $3^2 = 9$
2) Команда 2: $9 - 3 = 6$
3) Команда 1: $6^2 = 36$
4) Команда 2: $36 - 3 = 33$
5) Команда 2: $33 - 3 = 30$

Число $30$ получено из числа $3$ ровно за $5$ команд. Последовательность номеров команд: 12122.

Ответ: 12122

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