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

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

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

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

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

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

2. вычти 3

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

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

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

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

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

вычти 3

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

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

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

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

11221

Пояснение

Решение.

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

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

Шаг 1. Начнём с числа $100$ . Можно ли применить обратную команду №1? Да, из $100$ извлекается целый корень: $\sqrt{100} = 10$ .
Это соответствует прямой команде №1 (возведение в квадрат).
Текущее состояние: $100 \leftarrow 10$ (команда 1 в прямом порядке).

Шаг 2. Теперь работаем с числом $10$ . Извлечь корень (обратная команда №1) нельзя, так как $\sqrt{10}$ не является натуральным числом. Применим обратную команду №2: $10 + 3 = 13$ .
Текущее состояние: $10 \leftarrow 13$ (команда 2 в прямом порядке).

Однако, если мы продолжим прибавлять по $3$ , мы быстро превысим лимит в 5 команд. Попробуем другой путь на Шаге 1.

Шаг 1 (повторно). Снова начнём с $100$ . Применим обратную команду №2: $100 + 3 = 103$ . Из $103$ корень не извлекается. Это тупиковый путь, так как число будет только расти.

Шаг 2 (повторно). Вернёмся к числу $10$ . Мы уже поняли, что из $10$ нужно получить число, из которого извлекается корень, или которое можно получить из $2$ .
Попробуем применить обратную команду №2 ещё раз: $10 + 3 = 13$ . Снова не подходит.
Применим обратную команду №2 к числу $10$ еще раз: $13 + 3 = 16$ .
О! Из числа $16$ извлекается корень: $\sqrt{16} = 4$ .
Текущее состояние: $10 \leftarrow 13 \leftarrow 16$ (две команды №2 в прямом порядке).

Шаг 3. Работаем с числом $16$ . Применим обратную команду №1: $\sqrt{16} = 4$ .
Текущее состояние: $16 \leftarrow 4$ (команда 1 в прямом порядке).

Шаг 4. Работаем с числом $4$ . Применим обратную команду №1: $\sqrt{4} = 2$ .
Мы пришли к исходному числу $2$ !
Текущее состояние: $4 \leftarrow 2$ (команда 1 в прямом порядке).

Проверим полученный алгоритм в прямом порядке:
1. Число $2$ . Команда 1: $2^2 = 4$ .
2. Число $4$ . Команда 1: $4^2 = 16$ .
3. Число $16$ . Команда 2: $16 - 3 = 13$ .
4. Число $13$ . Команда 2: $13 - 3 = 10$ .
5. Число $10$ . Команда 1: $10^2 = 100$ .
Итого последовательность команд: 11221. Всего 5 команд, что соответствует условию.

Ответ: 11221

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