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

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

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

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

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

1. вычти 1

2. умножь на 3

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

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

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

умножь на 3

вычти 1

умножь на 3

вычти 1

вычти 1,

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

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

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

11211

Пояснение

Решение.

Нам необходимо из исходного числа $6$ получить число $10$ , используя не более 5 команд. Доступные команды: 1 (вычти 1) и 2 (умножь на 3).

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

Рассмотрим последовательность действий:

1. Начнём с числа $6$ . Применим команду №1 (вычти 1):
$6 - 1 = 5$ . (Команда 1)

2. К полученному числу $5$ применим команду №1 (вычти 1) ещё раз:
$5 - 1 = 4$ . (Команда 1)

3. Теперь у нас есть число $4$ . Применим команду №2 (умножь на 3):
$4 \cdot 3 = 12$ . (Команда 2)

4. Мы получили число $12$ , которое близко к цели. Применим команду №1 (вычти 1):
$12 - 1 = 11$ . (Команда 1)

5. Применим команду №1 (вычти 1) последний раз:
$11 - 1 = 10$ . (Команда 1)

Проверим количество команд: мы использовали 5 команд (1, 1, 2, 1, 1). Это соответствует условию "не более 5 команд".

Проверим цепочку вычислений ещё раз:
$6 \xrightarrow{1} 5 \xrightarrow{1} 4 \xrightarrow{2} 12 \xrightarrow{1} 11 \xrightarrow{1} 10$ .
Результат верный.

Запишем номера команд по порядку: 11211.

Ответ: 11211

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