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

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

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

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

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

1. вычти 1

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

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

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

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

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

вычти 1

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

вычти 1

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

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

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

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

21111

Пояснение

Решение.

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

Проанализируем конечную цель. Нам нужно получить число $5$ . Поскольку мы ограничены 5 командами и начинаем с маленького числа $3$ , попробуем рассуждать логически, двигаясь от начального числа к конечному.

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

Шаг 2. Теперь у нас число $9$ . Нам нужно прийти к $5$ . Самый простой способ уменьшить число — использовать команду 1.
$9 - 1 = 8$ (команда 1).

Шаг 3. Продолжаем уменьшать число $8$ , используя команду 1:
$8 - 1 = 7$ (команда 1).

Шаг 4. Продолжаем уменьшать число $7$ , используя команду 1:
$7 - 1 = 6$ (команда 1).

Шаг 5. Последний шаг, уменьшаем число $6$ до искомого:
$6 - 1 = 5$ (команда 1).

Проверим полученную последовательность команд: 2 (возведение в квадрат), 1 (вычитание), 1 (вычитание), 1 (вычитание), 1 (вычитание).
Вычисления: $3 \xrightarrow{2} 9 \xrightarrow{1} 8 \xrightarrow{1} 7 \xrightarrow{1} 6 \xrightarrow{1} 5$ .
Алгоритм состоит из 5 команд, что соответствует условию задачи.

Запишем номера команд по порядку: 2, 1, 1, 1, 1.

Ответ: 21111

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