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

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

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

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

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

1. вычти 1

2. умножь на 3

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

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

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

умножь на 3

вычти 1

умножь на 3

вычти 1

вычти 1,

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

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

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

11221

Пояснение

Решение.

Для решения этой задачи нам нужно найти последовательность из не более чем 5 команд, которая превратит число $9$ в число $62$ . У нас есть две команды:
1. вычти 1 (действие: $x - 1$ )
2. умножь на 3 (действие: $x \cdot 3$ )

Попробуем рассуждать от обратного: как из числа $62$ прийти к числу $9$ , используя обратные операции (прибавить $1$ и разделить на $3$ ). Это часто быстрее, так как деление на $3$ возможно не для каждого числа, что сужает выбор.

1. Число $62$ не делится на $3$ . Значит, на последнем шаге мы могли получить его только вычитанием единицы из какого-то числа.
Обратное действие: $62 + 1 = 63$ . (Команда 1)

2. Число $63$ делится на $3$ . Попробуем деление: $63 / 3 = 21$ . (Команда 2)

3. Число $21$ делится на $3$ . Попробуем деление: $21 / 3 = 7$ . (Команда 2)

4. Теперь нам нужно из числа $9$ (начальное число) получить число $7$ . Это легко сделать, дважды применив команду "вычти 1":
$9 - 1 = 8$ (Команда 1)
$8 - 1 = 7$ (Команда 1)

Теперь запишем все действия в прямом порядке от $9$ до $62$ :
Шаг 1: $9 - 1 = 8$ (Команда 1)
Шаг 2: $8 - 1 = 7$ (Команда 1)
Шаг 3: $7 \cdot 3 = 21$ (Команда 2)
Шаг 4: $21 \cdot 3 = 63$ (Команда 2)
Шаг 5: $63 - 1 = 62$ (Команда 1)

Проверим количество команд: использовано ровно $5$ команд, что соответствует условию задачи. Последовательность номеров команд: $11221$ .

Ответ: 11221

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