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

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

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

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

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

1. прибавь 3

2. умножь на 3

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

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

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

умножь на 3

прибавь 3

умножь на 3

прибавь 3

прибавь 3,

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

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

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

21221

Пояснение

Решение.

Нам необходимо составить алгоритм для исполнителя «Вычислитель», который превратит число $1$ в число $57$ ровно за $5$ шагов (или меньше), используя команды: «прибавь 3» (команда 1) и «умножь на 3» (команда 2).

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $57$ к исходному числу $1$ . При этом команды будут обратными: вместо «прибавь 3» будем использовать «вычти 3», а вместо «умножь на 3» — «раздели на 3».

Шаг 1. Последнее число — $57$ . Проверим, делится ли оно на $3$ .
$57 : 3 = 19$ . Число делится нацело, значит, последней командой могло быть умножение (команда 2).
Если же мы вычтем $3$ , получим: $57 - 3 = 54$ .
Попробуем идти через деление: $57 \xrightarrow{/3} 19$ . Это была команда 2.

Шаг 2. Теперь у нас число $19$ . Оно не делится на $3$ , поэтому единственный вариант — вычесть $3$ .
$19 - 3 = 16$ . Это была команда 1.

Шаг 3. Число $16$ . Оно не делится на $3$ , снова вычитаем $3$ .
$16 - 3 = 13$ . Это была команда 1.

Шаг 4. Число $13$ . Оно не делится на $3$ , вычитаем $3$ .
$13 - 3 = 10$ . Это была команда 1. (Замечаем, что мы отдаляемся от единицы слишком медленно, попробуем другой путь).

Вернемся к Шагу 1 и попробуем вычитание:
1) $57 - 3 = 54$ (команда 1).
2) $54$ делится на $3$ : $54 : 3 = 18$ (команда 2).
3) $18$ делится на $3$ : $18 : 3 = 6$ (команда 2).
4) $6$ делится на $3$ : $6 : 3 = 2$ (команда 2). Но нам нужно прийти к $1$ .
Попробуем на 4-м шаге вычесть: $18 - 3 = 15$ (команда 1).
5) $15 : 3 = 5$ или $15 - 3 = 12$ . Снова не получается $1$ за 5 шагов.

Попробуем еще раз, комбинируя команды:
1) $57 : 3 = 19$ (команда 2)
2) $19 - 3 = 16$ (команда 1) — не подходит.
Попробуем так:
1) $57 - 3 = 54$ (команда 1)
2) $54 : 3 = 18$ (команда 2)
3) $18 : 3 = 6$ (команда 2)
4) $6 : 3 = 2$ (команда 2)
5) $2$ — не подходит.

Правильный путь (проверка варианта 21221):
1) Начнем с $1$ . Применим команду 2 (умножь на 3): $1 \cdot 3 = 3$ .
2) Применим команду 1 (прибавь 3): $3 + 3 = 6$ .
3) Применим команду 2 (умножь на 3): $6 \cdot 3 = 18$ .
4) Применим команду 2 (умножь на 3): $18 \cdot 3 = 54$ .
5) Применим команду 1 (прибавь 3): $54 + 3 = 57$ .
Всего $5$ команд. Последовательность номеров: $2, 1, 2, 2, 1$ .

Ответ: 21221

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