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

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

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

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

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

1. вычти 1

2. умножь на 4

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

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

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

умножь на 4

вычти 1

умножь на 4,

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

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

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

21212

Пояснение

Решение.

Нам необходимо получить из числа $1$ число $44$ , используя не более 5 команд. У нас есть две команды:
1. вычти 1
2. умножь на 4

Для решения таких задач удобнее идти от конечного результата к начальному числу, используя обратные действия.
Обратные команды будут такими:
1. прибавь 1 (обратная к «вычти 1»)
2. раздели на 4 (обратная к «умножь на 4»)

Попробуем восстановить путь от $44$ к $1$ за 5 шагов:

Шаг 1. Число $44$ делится на $4$ . Применим обратную команду №2:
$44 : 4 = 11$ . (Команда №2 в прямом порядке)

Шаг 2. Число $11$ не делится на $4$ . Применим обратную команду №1:
$11 + 1 = 12$ . (Команда №1 в прямом порядке)

Шаг 3. Число $12$ делится на $4$ . Применим обратную команду №2:
$12 : 4 = 3$ . (Команда №2 в прямом порядке)

Шаг 4. Число $3$ не делится на $4$ . Применим обратную команду №1:
$3 + 1 = 4$ . (Команда №1 в прямом порядке)

Шаг 5. Число $4$ делится на $4$ . Применим обратную команду №2:
$4 : 4 = 1$ . (Команда №2 в прямом порядке)

Мы пришли к исходному числу $1$ . Теперь запишем команды в прямом порядке (от шага 5 к шагу 1):
1. Из $1$ получаем $4$ : умножить на $4$ (команда 2)
2. Из $4$ получаем $3$ : вычесть $1$ (команда 1)
3. Из $3$ получаем $12$ : умножить на $4$ (команда 2)
4. Из $12$ получаем $11$ : вычесть $1$ (команда 1)
5. Из $11$ получаем $44$ : умножить на $4$ (команда 2)

Проверим: $1 \xrightarrow{2} 4 \xrightarrow{1} 3 \xrightarrow{2} 12 \xrightarrow{1} 11 \xrightarrow{2} 44$ .
Алгоритм: 21212.

Ответ: 21212

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