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

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

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

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

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

1. прибавь 3

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

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

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

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

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

прибавь 3

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

прибавь 3

прибавь 3,

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

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

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

21111

Пояснение

Решение.

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

Будем рассуждать методом «от обратного» — попробуем прийти от конечного числа $48$ к начальному числу $6$ , используя обратные операции: вычитание $3$ и извлечение квадратного корня.

Шаг 1. Посмотрим на число $48$ . Извлечь корень из него нельзя (в натуральных числах), поэтому единственно возможный обратный шаг — вычитание $3$ .
$48 - 3 = 45$ (Команда 1 в прямом порядке).

Шаг 2. Из числа $45$ корень также не извлекается. Снова вычитаем $3$ .
$45 - 3 = 42$ (Команда 1 в прямом порядке).

Шаг 3. Из числа $42$ корень не извлекается. Вычитаем $3$ .
$42 - 3 = 39$ (Команда 1 в прямом порядке).

Шаг 4. Из числа $39$ корень не извлекается. Вычитаем $3$ .
$39 - 3 = 36$ (Команда 1 в прямом порядке).

Шаг 5. Из числа $36$ можно извлечь квадратный корень!
$\sqrt{36} = 6$ (Команда 2 в прямом порядке).

Мы пришли к исходному числу $6$ . Теперь запишем команды в прямом порядке (от $6$ к $48$ ):
1. Число $6$ . Применяем команду 2 (возведи в квадрат): $6^2 = 36$ .
2. Применяем команду 1 (прибавь $3$ ): $36 + 3 = 39$ .
3. Применяем команду 1 (прибавь $3$ ): $39 + 3 = 42$ .
4. Применяем команду 1 (прибавь $3$ ): $42 + 3 = 45$ .
5. Применяем команду 1 (прибавь $3$ ): $45 + 3 = 48$ .

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

Ответ: 21111

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