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

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

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

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

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

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

2. вычти 1

Первая из них возводит число на экране во вторую степень, вторая уменьшает его на 1.

Исполнитель работает только с натуральными числами.

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

(Например, 21221 $–$ это алгоритм:

вычти 1

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

вычти 1

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

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

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

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

12122

Пояснение

Решение.

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

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $62$ к исходному числу $3$ . При этом команды будут инвертированы:
1. Вместо возведения в квадрат — извлечение квадратного корня ( $\sqrt{x}$ );
2. Вместо вычитания единицы — прибавление единицы ( $x + 1$ ).

Шаг 1. Рассмотрим число $62$ . Из него нельзя извлечь целый квадратный корень, поэтому единственный вариант — прибавить $1$ .
$62 + 1 = 63$ . (Это была бы обратная команда 2).

Шаг 2. Из числа $63$ также нельзя извлечь корень. Прибавляем $1$ .
$63 + 1 = 64$ . (Это была бы обратная команда 2).

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

Шаг 4. Из числа $8$ нельзя извлечь целый корень. Прибавляем $1$ .
$8 + 1 = 9$ . (Это была бы обратная команда 2).

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

Теперь запишем команды в прямом порядке (от $3$ к $62$ ), заменяя обратные действия на исходные:
1. (Шаг 5 наоборот): Возведи в квадрат. $3^2 = 9$ . (Команда 1)
2. (Шаг 4 наоборот): Вычти 1. $9 - 1 = 8$ . (Команда 2)
3. (Шаг 3 наоборот): Возведи в квадрат. $8^2 = 64$ . (Команда 1)
4. (Шаг 2 наоборот): Вычти 1. $64 - 1 = 63$ . (Команда 2)
5. (Шаг 1 наоборот): Вычти 1. $63 - 1 = 62$ . (Команда 2)

Проверим последовательность команд 12122:
$3 \xrightarrow{1} 9 \xrightarrow{2} 8 \xrightarrow{1} 64 \xrightarrow{2} 63 \xrightarrow{2} 62$ .
Алгоритм состоит из 5 команд и приводит к нужному результату.

Ответ: 12122

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