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

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

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

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

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

1. вычти 1

2. умножь на 3

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

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

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

умножь на 3

вычти 1

умножь на 3

вычти 1

вычти 1,

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

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

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

11211

Пояснение

Решение.

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

Попробуем действовать методом подбора, анализируя возможные шаги. Поскольку конечное число $13$ не делится на $3$ , последней командой в алгоритме обязательно должно быть вычитание единицы (команда 1).

Рассмотрим последовательность действий:

1. Начнём с числа $7$ . Применим команду №1 (вычти 1):
$7 - 1 = 6$ .
Теперь у нас есть число $6$ .

2. К числу $6$ применим команду №1 (вычти 1):
$6 - 1 = 5$ .
Теперь у нас есть число $5$ .

3. К числу $5$ применим команду №2 (умножь на 3):
$5 \cdot 3 = 15$ .
Теперь у нас есть число $15$ .

4. К числу $15$ применим команду №1 (вычти 1):
$15 - 1 = 14$ .
Теперь у нас есть число $14$ .

5. К числу $14$ применим команду №1 (вычти 1):
$14 - 1 = 13$ .
Мы получили искомое число $13$ .

Проверим количество команд и их последовательность:
Шаг 1: команда 1 ( $7 \rightarrow 6$ )
Шаг 2: команда 1 ( $6 \rightarrow 5$ )
Шаг 3: команда 2 ( $5 \rightarrow 15$ )
Шаг 4: команда 1 ( $15 \rightarrow 14$ )
Шаг 5: команда 1 ( $14 \rightarrow 13$ )

Всего использовано 5 команд. Последовательность номеров команд: 11211.

Ответ: 11211

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