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

Решение.

Нам необходимо составить алгоритм для исполнителя, который с помощью команд «умножь на 5» (команда 1) и «прибавь 2» (команда 2) превратит число $1$ в число $39$. При этом алгоритм должен содержать не более 5 команд.

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

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

Шаг 2. Число $37$ также не делится на 5. Снова применяем обратную команду 2:
$37 - 2 = 35$ (команда 2 в обратном порядке).

Шаг 3. Число $35$ делится на 5. Попробуем применить обратную команду 1:
$35 : 5 = 7$ (команда 1 в обратном порядке).

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

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

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

Проверим полученную последовательность команд 12122:
$1 \cdot 5 = 5$
$5 + 2 = 7$
$7 \cdot 5 = 35$
$35 + 2 = 37$
$37 + 2 = 39$

Алгоритм верный и содержит 5 команд.

Ответ: 12122

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