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

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

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

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

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

1. умножь на 4

2. вычти 2

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

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

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

умножь на 4

вычти 2

умножь на 4,

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

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

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

21122

Пояснение

Решение. Для решения этой задачи нам нужно найти последовательность из не более чем 5 команд, которая превратит число $4$ в число $28$ . У нас есть две команды:
1. Умножить на $4$ ( $\times 4$ )
2. Вычесть $2$ ( $- 2$ )

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

Шаг 1. Применим команду 2 (вычти 2):
$4 - 2 = 2$ (команда 2).
Теперь у нас число $2$ .

Шаг 2. Применим команду 1 (умножь на 4):
$2 \times 4 = 8$ (команда 1).
Теперь у нас число $8$ .

Шаг 3. Применим команду 1 (умножь на 4):
$8 \times 4 = 32$ (команда 1).
Теперь у нас число $32$ . Мы уже близко к цели ( $28$ ).

Шаг 4. Чтобы из $32$ получить $28$ , нужно вычесть $4$ . Так как команда 2 вычитает по $2$ , нам нужно применить её дважды.
Применим команду 2:
$32 - 2 = 30$ (команда 2).

Шаг 5. Применим команду 2 еще раз:
$30 - 2 = 28$ (команда 2).
Цель достигнута!

Проверим всю цепочку вычислений:
$4 \xrightarrow{2} 2 \xrightarrow{1} 8 \xrightarrow{1} 32 \xrightarrow{2} 30 \xrightarrow{2} 28$ .
Последовательность команд: 2, 1, 1, 2, 2. Всего использовано 5 команд, что соответствует условию задачи.

Ответ: 21122

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