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

Решение.

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

Будем решать задачу методом "от обратного" — попробуем прийти от конечного числа $37$ к начальному числу $3$. При этом команды будут инвертированы:
1. вместо "умножь на 3" будем выполнять "раздели на 3" (если число делится нацело);
2. вместо "прибавь 4" будем выполнять "вычти 4".

Шаг 1. Рассмотрим число $37$.
Оно не делится на $3$ без остатка, поэтому мы можем применить только обратную команду №2:
$37 - 4 = 33$. (Это была команда 2 в прямом порядке).

Шаг 2. Рассмотрим число $33$.
Здесь у нас есть выбор: вычесть 4 или разделить на 3.
Попробуем разделить на 3 (обратная команда №1):
$33 : 3 = 11$. (Это была команда 1 в прямом порядке).

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

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

Мы пришли к исходному числу $3$. Теперь запишем команды в прямом порядке (от первого шага к последнему, но с конца нашего рассуждения):
1. Число $3$, команда 2: $3 + 4 = 7$
2. Число $7$, команда 2: $7 + 4 = 11$
3. Число $11$, команда 1: $11 \cdot 3 = 33$
4. Число $33$, команда 2: $33 + 4 = 37$

Алгоритм состоит из 4 команд: 2, 2, 1, 2.

Ответ: 2212

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