Задание 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. вычти 1

2. умножь на 2

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

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

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

вычти 1

умножь на 2

вычти 1

умножь на 2

вычти 1,

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

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

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

21221

Пояснение

Решение.

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

Для решения таких задач удобнее идти от обратного: от конечного числа $11$ к начальному числу $2$ . При этом команды будут инвертированы: вместо "вычти 1" будем "прибавлять 1", а вместо "умножь на 2" будем "делить на 2" (если число четное).

Попробуем восстановить путь с конца:

1) Число $11$ не делится на $2$ , значит, на последнем шаге мы могли получить его только прибавлением единицы (обратная команда 1).
$11 - 1 = 10$ (Команда 1 в прямом порядке была последней).

2) Число $10$ делится на $2$ . Попробуем деление (обратная команда 2):
$10 / 2 = 5$ (Команда 2 в прямом порядке была предпоследней).

3) Число $5$ не делится на $2$ , значит, используем обратную команду 1:
$5 - 1 = 4$ (Команда 1 в прямом порядке).

4) Число $4$ делится на $2$ . Используем обратную команду 2:
$4 / 2 = 2$ (Команда 2 в прямом порядке).

5) Мы получили начальное число $2$ . Однако мы использовали всего 4 шага. Проверим условие: нам нужно получить из $2$ число $11$ . Если мы просто выполним эти действия, получится: $2 \cdot 2 = 4$ , $4 - 1 = 3$ , $3 \cdot 2 = 6$ , $6 + 1 = 7$ — это не приводит к $11$ . Значит, нужно найти путь ровно из 5 команд, который даст $11$ .

Попробуем другой путь от числа $2$ к $11$ в прямом порядке, учитывая, что нам нужно "расти":
Шаг 1: $2 \cdot 2 = 4$ (Команда 2)
Шаг 2: $4 - 1 = 3$ (Команда 1)
Шаг 3: $3 \cdot 2 = 6$ (Команда 2)
Шаг 4: $6 \cdot 2 = 12$ (Команда 2)
Шаг 5: $12 - 1 = 11$ (Команда 1)

Проверим полученную последовательность команд: 21221.
1) $2 \cdot 2 = 4$
2) $4 - 1 = 3$
3) $3 \cdot 2 = 6$
4) $6 \cdot 2 = 12$
5) $12 - 1 = 11$
Алгоритм состоит из 5 команд и приводит к числу 11.

Ответ: 21221

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