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

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

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

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

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

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

2. вычти 5

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

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

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

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

вычти 5

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

вычти 5

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

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

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

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

12122

Пояснение

Решение.

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

Будем строить цепочку вычислений пошагово, применяя команды к исходному числу $3$ :

Шаг 1. Применим команду №1 (возведи в квадрат):
$3^2 = 9$ .
(Если бы мы применили команду №2, то получили бы $3 - 5 = -2$ , но по условию исполнитель работает только с натуральными числами, поэтому этот путь невозможен).

Шаг 2. У нас есть число $9$ . Применим команду №2 (вычти 5):
$9 - 5 = 4$ .
(Если возвести $9$ в квадрат, получится $81$ , что слишком далеко от искомого числа $6$ ).

Шаг 3. У нас есть число $4$ . Применим команду №1 (возведи в квадрат):
$4^2 = 16$ .

Шаг 4. У нас есть число $16$ . Применим команду №2 (вычти 5):
$16 - 5 = 11$ .

Шаг 5. У нас есть число $11$ . Применим команду №2 (вычти 5):
$11 - 5 = 6$ .

Мы получили число $6$ ровно за $5$ команд. Запишем последовательность номеров выполненных команд: 1 (квадрат), 2 (вычитание), 1 (квадрат), 2 (вычитание), 2 (вычитание).

Проверим итоговую последовательность: $3 \xrightarrow{1} 9 \xrightarrow{2} 4 \xrightarrow{1} 16 \xrightarrow{2} 11 \xrightarrow{2} 6$ .

Ответ: 12122

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