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

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

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

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

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

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

2. вычти 1

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

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

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

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

вычти 1

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

вычти 1

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

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

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

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

12112

Пояснение

Решение.

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

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

Проследим путь от $80$ к $2$ за $5$ шагов:

Шаг 5. Число $80$ . Из него нельзя извлечь целый квадратный корень, значит, единственно возможный обратный шаг — прибавить $1$ .
$80 + 1 = 81$ . (Команда №2 в прямом порядке)

Шаг 4. Число $81$ . Здесь мы можем извлечь корень: $\sqrt{81} = 9$ . Это значительно приближает нас к числу $2$ .
$81 \rightarrow 9$ . (Команда №1 в прямом порядке)

Шаг 3. Число $9$ . Снова можно извлечь корень: $\sqrt{9} = 3$ .
$9 \rightarrow 3$ . (Команда №1 в прямом порядке)

Шаг 2. Число $3$ . Корень не извлекается. Прибавляем $1$ :
$3 + 1 = 4$ . (Команда №2 в прямом порядке)

Шаг 1. Число $4$ . Извлекаем корень: $\sqrt{4} = 2$ .
$4 \rightarrow 2$ . (Команда №1 в прямом порядке)

Мы пришли к исходному числу $2$ . Теперь запишем команды в прямом порядке (от $2$ к $80$ ):
1. Число $2$ . Возводим в квадрат (команда 1): $2^2 = 4$ .
2. Число $4$ . Вычитаем 1 (команда 2): $4 - 1 = 3$ .
3. Число $3$ . Возводим в квадрат (команда 1): $3^2 = 9$ .
4. Число $9$ . Возводим в квадрат (команда 1): $9^2 = 81$ .
5. Число $81$ . Вычитаем 1 (команда 2): $81 - 1 = 80$ .

Последовательность команд: 1, 2, 1, 1, 2.

Ответ: 12112

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