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

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

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

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

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

1. прибавь 3

2. умножь на 3

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

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

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

умножь на 3

прибавь 3

умножь на 3

прибавь 3

прибавь 3,

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

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

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

11122

Пояснение

Решение.

Нам необходимо составить алгоритм из 5 команд, который превращает число $1$ в число $90$ . У нас есть две команды:
1. Прибавь $3$
2. Умножь на $3$

Чтобы найти кратчайший путь (или путь из фиксированного количества шагов), удобнее рассуждать «с конца» — от итогового числа $90$ к исходному числу $1$ . При движении назад команды меняются на противоположные:
1. Вычти $3$
2. Раздели на $3$

Попробуем восстановить последовательность шагов от $90$ к $1$ :
Шаг 5: Число $90$ . Оно делится на $3$ , поэтому применим обратную команду №2 (разделить на $3$ ).
$90 : 3 = 30$ . (Команда №2)

Шаг 4: Число $30$ . Оно также делится на $3$ , применим обратную команду №2.
$30 : 3 = 10$ . (Команда №2)

Шаг 3: Число $10$ . Оно не делится на $3$ нацело, поэтому мы можем применить только обратную команду №1 (вычти $3$ ).
$10 - 3 = 7$ . (Команда №1)

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

Шаг 1: Число $4$ . Применяем обратную команду №1.
$4 - 3 = 1$ . (Команда №1)

Мы пришли к исходному числу $1$ ровно за 5 шагов. Теперь запишем команды в прямом порядке (от $1$ к $90$ ):
1. $1 + 3 = 4$ (Команда 1)
2. $4 + 3 = 7$ (Команда 1)
3. $7 + 3 = 10$ (Команда 1)
4. $10 \cdot 3 = 30$ (Команда 2)
5. $30 \cdot 3 = 90$ (Команда 2)

Последовательность номеров команд: $11122$ .

Ответ: 11122

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