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

Решение.

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

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

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

Шаг 1. Из числа $49$ можно извлечь квадратный корень: $\sqrt{49} = 7$. Это соответствует обратной команде №1. Значит, последней командой в прямом алгоритме была команда 1.
Текущее число: $7$.

Шаг 2. Из числа $7$ нельзя извлечь целый квадратный корень. Поэтому используем вторую обратную команду — прибавим 2: $7 + 2 = 9$. Это соответствует обратной команде №2. Значит, предпоследней командой была команда 2.
Текущее число: $9$.

Шаг 3. Из числа $9$ можно извлечь квадратный корень: $\sqrt{9} = 3$. Это соответствует обратной команде №1. Значит, третьей с конца была команда 1.
Текущее число: $3$.

Шаг 4. Из числа $3$ нельзя извлечь целый корень (корень из 1 мы не рассматриваем, так как нам нужно прийти к 1 за 5 шагов, а не за 4). Прибавим 2: $3 + 2 = 5$. Это соответствует обратной команде №2.
Текущее число: $5$.

Шаг 5. Из числа $5$ прибавим 2: $5 + 2 = 7$. Это не ведет к 1. Попробуем другой путь на шаге 4.

Вернемся к числу $3$ (результат шага 3). Нам нужно получить $3$ из $1$ за две команды.
Если мы идем от $1$ к $3$:
1) $1 - 2 = -1$ (не подходит);
2) $1^2 = 1$ (не меняет число);
Попробуем прибавлять 2 к единице:
1) $1 + 2 = 3$ (команда 2);
2) $3 + 2 = 5$ (не подходит).
Посмотрим на последовательность команд в прямом порядке, чтобы получить $49$ из $1$:
1. Начнем с $1$. Применим команду 2: $1 - 2 = -1$.
2. Применим команду 2: $-1 - 2 = -3$.
Это не ведет к успеху.

Пересмотрим путь от $49$ назад внимательнее:
$49 \xrightarrow{\sqrt{x}} 7 \xrightarrow{+2} 9 \xrightarrow{\sqrt{x}} 3 \xrightarrow{+2} 5 \xrightarrow{+2} 7$ — не подходит.
Попробуем иначе: $49 \xrightarrow{\sqrt{x}} 7 \xrightarrow{+2} 9 \xrightarrow{+2} 11 \dots$ — тоже не подходит.

Попробуем идти от $1$ вперед, используя 5 команд:
1) Команда 2: $1 - 2 = -1$
2) Команда 2: $-1 - 2 = -3$
3) Команда 1: $(-3)^2 = 9$
4) Команда 2: $9 - 2 = 7$
5) Команда 1: $7^2 = 49$

Проверим полученную последовательность команд 22121:
1. $1 - 2 = -1$ (команда 2)
2. $-1 - 2 = -3$ (команда 2)
3. $(-3)^2 = 9$ (команда 1)
4. $9 - 2 = 7$ (команда 2)
5. $7^2 = 49$ (команда 1)

Алгоритм содержит ровно 5 команд и приводит к числу 49.

Ответ: 22121

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