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

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

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

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

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

1. вычти 1

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

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

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

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

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

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

вычти 1

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

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

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

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

12211

Пояснение

Решение.

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

Попробуем действовать методом «от обратного» — из конечного числа $14$ прийти к начальному числу $3$ . При движении назад команды меняются на противоположные:
1. прибавь 1 (вместо «вычти 1»)
2. извлеки квадратный корень (вместо «возведи в квадрат»)

Проанализируем шаги с конца:
1) Число $14$ . Из него нельзя извлечь целый корень, значит, последним действием была команда 1. Прибавим 1: $14 + 1 = 15$ .
2) Число $15$ . Снова нельзя извлечь корень. Прибавим 1: $15 + 1 = 16$ .
3) Число $16$ . Здесь мы можем извлечь корень: $\sqrt{16} = 4$ . Это выгодно, так как число быстро уменьшается.
4) Число $4$ . Снова можем извлечь корень: $\sqrt{4} = 2$ .
5) Число $2$ . Чтобы получить исходную тройку, прибавим 1: $2 + 1 = 3$ .

Теперь запишем полученную последовательность действий в прямом порядке (от $3$ к $14$ ):
Шаг 1: Число $3$ . Применяем команду 1 (вычти 1): $3 - 1 = 2$ .
Шаг 2: Число $2$ . Применяем команду 2 (возведи в квадрат): $2^2 = 4$ .
Шаг 3: Число $4$ . Применяем команду 2 (возведи в квадрат): $4^2 = 16$ .
Шаг 4: Число $16$ . Применяем команду 1 (вычти 1): $16 - 1 = 15$ .
Шаг 5: Число $15$ . Применяем команду 1 (вычти 1): $15 - 1 = 14$ .

Проверим количество команд: их ровно 5, что соответствует условию задачи. Последовательность номеров команд: 1, 2, 2, 1, 1.

Ответ: 12211

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