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

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

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

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

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

1. прибавить 2

2. удвоить

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

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

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

прибавить 2

удвоить

прибавить 2

удвоить

удвоить,

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

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

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

12212

Пояснение

Решение.

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

Для решения таких задач удобнее всего двигаться «с конца» — от числа $44$ к числу $3$ . При этом действия заменяются на обратные: вместо «прибавить $2$ » будем «вычитать $2$ », а вместо «удвоить» — «делить на $2$ » (если число четное).

Шаг 1. Начнём с числа $44$ . Оно чётное, поэтому его можно разделить на $2$ . $44 : 2 = 22$ (команда 2 в обратном порядке). Если бы мы вычли $2$ , получили бы $42$ , что тоже возможно, но деление быстрее уменьшает число.

Шаг 2. Теперь у нас число $22$ . Оно также чётное, разделим его на $2$ . $22 : 2 = 11$ (команда 2 в обратном порядке).

Шаг 3. Число $11$ нечётное, на $2$ не делится. Единственный вариант — вычесть $2$ . $11 - 2 = 9$ (команда 1 в обратном порядке).

Шаг 4. Число $9$ нечётное, вычитаем $2$ . $9 - 2 = 7$ (команда 1 в обратном порядке).

Шаг 5. Число $7$ нечётное, вычитаем $2$ . $7 - 2 = 5$ (команда 1 в обратном порядке). Мы не пришли к числу $3$ за 5 шагов. Значит, нужно изменить стратегию на предыдущих этапах.

Попробуем другой путь: 1) $44 : 2 = 22$ (обратная команде 2) 2) $22 : 2 = 11$ (обратная команде 2) 3) $11 - 2 = 9$ (обратная команде 1) Стоп, если мы на шаге 2 вычтем $2$ вместо деления? 1) $44 : 2 = 22$ (обратная команде 2) 2) $22 - 2 = 20$ (обратная команде 1) 3) $20 : 2 = 10$ (обратная команде 2) 4) $10 : 2 = 5$ — не подходит. Попробуем: 1) $44 : 2 = 22$ (обратная команде 2) 2) $22 - 2 = 20$ (обратная команде 1) 3) $20 - 2 = 18$ (обратная команде 1) 4) $18 : 2 = 9$ — не подходит.

Вернёмся к прямой последовательности команд, проверяя ответ 12212: 1. Команда 1: $3 + 2 = 5$ 2. Команда 2: $5 \cdot 2 = 10$ 3. Команда 2: $10 \cdot 2 = 20$ 4. Команда 1: $20 + 2 = 22$ 5. Команда 2: $22 \cdot 2 = 44$

Проверим количество команд: их ровно $5$ . Результат совпадает с требуемым числом $44$ . Последовательность номеров команд: $1, 2, 2, 1, 2$ .

Ответ: 12212

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