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

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

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

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

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

1. умножь на 4

2. вычти 4

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

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

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

умножь на 4

вычти 4

умножь на 4,

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

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

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

11122

Пояснение

Решение.

Нам необходимо составить алгоритм для исполнителя «Вычислитель», который преобразует число $2$ в число $120$ за ограниченное количество шагов (не более 5). У исполнителя есть две команды:
1. умножь на 4 (действие: $\cdot 4$ );
2. вычти 4 (действие: $- 4$ ).

Для решения таких задач удобно использовать метод «обратного хода» — будем двигаться от конечного числа $120$ к начальному числу $2$ . При этом команды заменяются на противоположные:
1. Вместо «умножь на 4» выполняем «раздели на 4» (если число делится на 4 без остатка);
2. Вместо «вычти 4» выполняем «прибавь 4».

Шаг 1. Начнём с числа $120$ . Оно делится на 4. Проверим деление: $120 : 4 = 30$ . Это значительно приближает нас к начальному числу $2$ .
Команда (обратная): разделить на 4. (Соответствует прямой команде 1).

Шаг 2. Теперь у нас число $30$ . Оно не делится на 4 без остатка ( $30 : 4 = 7,5$ ). Значит, единственный путь — прибавить 4.
$30 + 4 = 34$ .
Команда (обратная): прибавить 4. (Соответствует прямой команде 2).

Шаг 3. Число $34$ также не делится на 4. Прибавляем 4 еще раз:
$34 + 4 = 38$ .
Команда (обратная): прибавить 4. (Соответствует прямой команде 2).

Видим, что мы отдаляемся от цели $2$ . Попробуем изменить стратегию на первом шаге. Если мы не будем делить $120$ на 4 сразу, а сначала прибавим 4, число станет еще больше. Значит, первый шаг был верным. Попробуем рассмотреть прямую последовательность команд, зная, что в конце должно быть умножение на 4 или вычитание 4.

Проверим последовательность, указанную в условии как правильную: 11122.
1. Число $2$ . Команда 1: $2 \cdot 4 = 8$ .
2. Число $8$ . Команда 1: $8 \cdot 4 = 32$ .
3. Число $32$ . Команда 1: $32 \cdot 4 = 128$ .
4. Число $128$ . Команда 2: $128 - 4 = 124$ .
5. Число $124$ . Команда 2: $124 - 4 = 120$ .

Проверка расчётов:
$((2 \cdot 4) \cdot 4) \cdot 4 - 4 - 4 = 120$
$8 \cdot 4 \cdot 4 - 4 - 4 = 120$
$32 \cdot 4 - 4 - 4 = 120$
$128 - 4 - 4 = 120$
$124 - 4 = 120$ .
Алгоритм состоит из 5 команд и приводит к верному результату.

Ответ: 11122

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