Задание 5

Анализировать простые алгоритмы для конкретного исполнителя с фиксированным набором команд · 103 задания

Задание №5
№5
У исполнителя Квадратор две команды, которым присвоены номера: 1. возведи в квадрат 2. вычти 4 Первая из них возводит число на экране во вторую степен…
Анализ алгоритма
Задание №5
№5
У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 2 2. умножь на 3 Первая из них уменьшает число на экране на 2, вторая утраивае…
Анализ алгоритма
Задание №5
№5
У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая утраивае…
Анализ алгоритма
Задание №5
№5
У исполнителя Вычислитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая утраив…
Анализ алгоритма
Задание №5
№5
У исполнителя Вычислитель две команды, которым присвоены номера: 1. вычесть 4 2. приписать 2 Первая из них уменьшает число на 4, а вторая приписывает…
Анализ алгоритма
Задание №5
№5
У исполнителя Квадратор две команды, которым присвоены номера: 1. возведи в квадрат 2. зачеркни справа Первая из них возводит число на экране во втору…
Анализ алгоритма
Задание №5
№5
У исполнителя Вычислитель две команды, которым присвоены номера: 1. умножь на 3 2. прибавь 2 Первая из них увеличивает число на экране в 3 раза, втора…
Анализ алгоритма
Задание №5
№5
У исполнителя Квадратор две команды, которым присвоены номера: 1. возведи в квадрат 2. вычти 4 Первая из них возводит число на экране во вторую степен…
Анализ алгоритма
Задание №5
№5
У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 1 2. умножь на 3 Первая из них уменьшает число на экране на 1, вторая утраивае…
Анализ алгоритма
Задание №5
№5
У исполнителя Квадратор две команды, которым присвоены номера: 1. прибавь 1 2. возведи в квадрат Первая из них увеличивает число на экране на 1, втора…
Анализ алгоритма
Задание №5
№5
У исполнителя Вычислитель две команды, которым присвоены номера: 1. вычти 3 2. умножь на 5 Первая из них уменьшает число на экране на 3, вторая увелич…
Анализ алгоритма
Задание №5
№5
У исполнителя Вычислитель две команды, которым присвоены номера: 1. умножь на 4 2. прибавь 3 Первая из них увеличивает число на экране в 4 раза, втора…
Анализ алгоритма

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

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

1. возведи в квадрат

2. прибавь 3

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

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

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

возведи в квадрат

прибавь 3

возведи в квадрат,

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

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

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

21222

Пояснение

Решение.

Нам необходимо составить алгоритм для исполнителя Квадратор, который преобразует число $1$ в число $25$ за ограниченное количество шагов (не более 5 команд). У исполнителя есть две команды:
1. возведи в квадрат (обозначим как $x^2$ );
2. прибавь 3 (обозначим как $x + 3$ ).

Будем решать задачу методом обратного хода — от конечного числа $25$ к начальному числу $1$ . Это удобнее, так как количество возможных действий на каждом шаге уменьшается. Обратные команды будут такими:
1. извлеки квадратный корень ( $\sqrt{x}$ );
2. вычти 3 ( $x - 3$ ).

Шаг 1. Начнем с числа $25$ .
Из числа $25$ можно извлечь корень: $\sqrt{25} = 5$ (команда 1).
Или можно вычесть 3: $25 - 3 = 22$ (команда 2).
Попробуем пойти по пути извлечения корня (команда 1 в обратном порядке соответствует команде 1 в прямом).

Шаг 2. У нас число $5$ .
Корень из $5$ не извлекается нацело, поэтому используем только вычитание:
$5 - 3 = 2$ (команда 2).

Шаг 3. У нас число $2$ .
Корень из $2$ не извлекается нацело. Вычитаем 3:
$2 - 3 = -1$ . Это число меньше начального ( $1$ ), значит, этот путь тупиковый. Вернемся назад.

Попробуем другой путь (начиная с конца):
1. $25 - 3 = 22$ (команда 2)
2. $22 - 3 = 19$ (команда 2)
3. $19 - 3 = 16$ (команда 2)
4. Из $16$ можно извлечь корень: $\sqrt{16} = 4$ (команда 1)
5. Из $4$ можно извлечь корень: $\sqrt{4} = 2$ (команда 1). Опять не приходим к $1$ .
Или из $4$ вычесть 3: $4 - 3 = 1$ (команда 2). Это подходит!

Запишем полученную последовательность обратных действий: $25 \xrightarrow{-3} 22 \xrightarrow{-3} 19 \xrightarrow{-3} 16 \xrightarrow{\sqrt{}} 4 \xrightarrow{-3} 1$ .
Теперь запишем эти команды в прямом порядке (от $1$ к $25$ ) и заменим их на номера из условия:
1. $1 + 3 = 4$ (команда 2)
2. $4^2 = 16$ (команда 1)
3. $16 + 3 = 19$ (команда 2)
4. $19 + 3 = 22$ (команда 2)
5. $22 + 3 = 25$ (команда 2)

Проверим количество команд: их ровно 5. Последовательность номеров команд: 2, 1, 2, 2, 2.

Ответ: 21222

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