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

Решение.

Нам необходимо получить из числа $3$ число $39$, используя не более 5 команд. У нас есть две команды:
1. умножь на 4 (действие: $\cdot 4$)
2. вычти 1 (действие: $- 1$)

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

Попробуем восстановить путь от $39$ к $3$:
Шаг 1. Число $39$ не делится на $4$. Значит, последней командой могла быть только команда 2 (вычти 1). Выполняем обратное действие: $39 + 1 = 40$. (Команда в ответе будет стоять последней).
Шаг 2. Число $40$ делится на $4$. Попробуем деление: $40 : 4 = 10$. (Это обратная команда для команды 1).
Шаг 3. Число $10$ не делится на $4$. Применяем обратную команду 2: $10 + 1 = 11$.
Шаг 4. Число $11$ не делится на $4$. Применяем обратную команду 2: $11 + 1 = 12$.
Шаг 5. Число $12$ делится на $4$. Применяем обратную команду 1: $12 : 4 = 3$. Мы пришли к исходному числу!

Теперь запишем команды в прямом порядке (от $3$ к $39$):
1. (Шаг 5 наоборот) Число $3$, команда 1: $3 \cdot 4 = 12$
2. (Шаг 4 наоборот) Число $12$, команда 2: $12 - 1 = 11$
3. (Шаг 3 наоборот) Число $11$, команда 2: $11 - 1 = 10$
4. (Шаг 2 наоборот) Число $10$, команда 1: $10 \cdot 4 = 40$
5. (Шаг 1 наоборот) Число $40$, команда 2: $40 - 1 = 39$

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

Ответ: 12212

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