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

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

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

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

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

1. вычти 1

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

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

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

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

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

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

вычти 1

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

вычти 1,

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

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

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

11221

Пояснение

Решение.

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

Для решения таких задач удобнее идти от конечного результата к начальному числу, используя обратные операции. Обратной операцией для вычитания $1$ является прибавление $1$ , а для возведения в квадрат — извлечение квадратного корня.

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

Шаг 1. Число $80$ не является полным квадратом, поэтому мы не можем применить обратную команду "извлеки корень". Значит, на последнем шаге была выполнена прямая команда 1 (вычти $1$ ).
Выполняем обратное действие: $80 + 1 = 81$ . (Команда 1)

Шаг 2. Число $81$ является полным квадратом ( $9^2 = 81$ ). Выгодно применить обратную команду "извлеки корень", так как это значительно уменьшает число и приближает нас к $5$ .
Выполняем обратное действие: $\sqrt{81} = 9$ . (Команда 2)

Шаг 3. Число $9$ также является полным квадратом ( $3^2 = 9$ ). Однако, если мы извлечем корень, то получим $3$ , что уже меньше нашего начального числа $5$ . Нам нужно получить $5$ , поэтому попробуем использовать обратное действие для вычитания.
Выполняем обратное действие: $9 + 1 = 10$ . (Команда 1)

Шаг 4. Число $10$ не является квадратом.
Выполняем обратное действие: $10 + 1 = 11$ . (Команда 1)

Шаг 5. Проверим, можем ли мы прийти к числу $5$ за оставшиеся шаги. Если мы прибавим еще единицу, получим $11 + 1 = 12$ , что не ведет к $5$ .
Вернемся к Шагу 3 и попробуем другой путь. Нам нужно получить $81$ из $5$ за $4$ команды.
1) $5 - 1 = 4$ (Команда 1)
2) $4 - 1 = 3$ (Команда 1)
3) $3^2 = 9$ (Команда 2)
4) $9^2 = 81$ (Команда 2)
5) $81 - 1 = 80$ (Команда 1)

Проверим полученную последовательность команд $11221$ :
1. Число $5$ , команда 1: $5 - 1 = 4$
2. Число $4$ , команда 1: $4 - 1 = 3$
3. Число $3$ , команда 2: $3^2 = 9$
4. Число $9$ , команда 2: $9^2 = 81$
5. Число $81$ , команда 1: $81 - 1 = 80$

Алгоритм $11221$ за $5$ команд превращает $5$ в $80$ .

Ответ: 11221

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