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

К списку заданий

#55899Задание №5ФИПИ

Анализ алгоритма

У исполнителя Квадратор две команды, которым присвоены номера:

1. возведи в квадрат

2. вычти 3

Первая из них возводит число на экране во вторую степень, вторая $–$ вычитает из числа 3.

Составьте алгоритм получения из числа 1 числа 19, содержащий не более 5 команд. В ответе запишите только номера команд.

(Например, 12221 $–$ это

алгоритм

возведи в квадрат

вычти 3

возведи в квадрат

который преобразует число 4 в 49.)

Если таких алгоритмов более одного, то запишите любой из них.

Правильный ответ

22122

Пояснение

Решение.

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

Поскольку нам нужно получить число $19$ , а возведение в квадрат очень быстро увеличивает числа, удобнее всего рассуждать «от обратного» — из конечного числа $19$ прийти к начальному числу $1$ . При этом команды будут инвертированы:
1. Извлеки квадратный корень ( $\sqrt{x}$ );
2. Прибавь 3 ( $x + 3$ ).

Шаг 1. Начнём с числа $19$ . Извлечь корень из $19$ нельзя (не получится целое число), поэтому применяем обратную команду №2 (прибавляем 3):
$19 + 3 = 22$ . (Это была бы команда 2, если идти от 1 к 19).

Шаг 2. Из числа $22$ корень не извлекается. Снова прибавляем 3:
$22 + 3 = 25$ . (Снова команда 2).

Шаг 3. Из числа $25$ можно извлечь квадратный корень:
$\sqrt{25} = 5$ . (Это соответствует прямой команде №1).

Шаг 4. Из числа $5$ корень не извлекается. Прибавляем 3:
$5 + 3 = 8$ . (Команда 2).

Шаг 5. Из числа $8$ корень не извлекается. Прибавляем 3:
$8 + 3 = 11$ . (Это тупиковый путь, так как мы не пришли к 1 за 5 шагов).

Попробуем другой путь. Вернёмся к числу $5$ на шаге 3 и попробуем получить его из $1$ прямым ходом:
1. Начнём с $1$ .
2. Применим команду №2? Нет, $1 - 3 = -2$ , это не поможет. Применим команду №2 дважды? Нет.
3. Попробуем идти от $1$ вперёд, зная, что нам нужно попасть в «удобные» числа.

Прямой ход:
1. Начнём с числа $1$ . Применим команду №2 (вычти 3): $1 - 3 = -2$ .
2. Применим команду №1 (возведи в квадрат): $(-2)^2 = 4$ .
3. Применим команду №1 (возведи в квадрат): $4^2 = 16$ .
4. Применим команду №2 (вычти 3): $16 - 3 = 13$ . (Не подходит).

Ещё одна попытка прямого хода:
1. Команда 2: $1 - 3 = -2$ .
2. Команда 2: $-2 - 3 = -5$ .
3. Команда 1: $(-5)^2 = 25$ .
4. Команда 2: $25 - 3 = 22$ .
5. Команда 2: $22 - 3 = 19$ .

Проверим последовательность команд: 2 (вычли 3), 2 (вычли 3), 1 (квадрат), 2 (вычли 3), 2 (вычли 3).
Вычисления: $1 \xrightarrow{2} -2 \xrightarrow{2} -5 \xrightarrow{1} 25 \xrightarrow{2} 22 \xrightarrow{2} 19$ .
Алгоритм содержит ровно 5 команд и приводит к числу 19.

Ответ: 22122

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