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

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

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

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

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

1. прибавь 3

2. умножь на 2

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

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

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

прибавь 3

умножь на 2

прибавь 3

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

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

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

21212

Пояснение

Решение.

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

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

Шаг 1. Последнее число — $50$ . Оно делится на $2$ . Попробуем применить обратную команду 2 (деление):
$50 : 2 = 25$ . (Это была команда 2, если смотреть от начала).

Шаг 2. Число $25$ не делится на $2$ , поэтому мы можем применить только обратную команду 1 (вычитание):
$25 - 3 = 22$ . (Это была команда 1).

Шаг 3. Число $22$ делится на $2$ . Попробуем применить обратную команду 2:
$22 : 2 = 11$ . (Это была команда 2).

Шаг 4. Число $11$ не делится на $2$ , применяем обратную команду 1:
$11 - 3 = 8$ . (Это была команда 1).

Шаг 5. Число $8$ делится на $2$ . Применим обратную команду 2:
$8 : 2 = 4$ . (Это была команда 2).

Мы пришли к исходному числу $4$ ровно за $5$ шагов. Теперь запишем команды в прямом порядке (от числа $4$ к числу $50$ ):
1. $4 \cdot 2 = 8$ (команда 2)
2. $8 + 3 = 11$ (команда 1)
3. $11 \cdot 2 = 22$ (команда 2)
4. $22 + 3 = 25$ (команда 1)
5. $25 \cdot 2 = 50$ (команда 2)

Последовательность команд: 21212.

Ответ: 21212

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