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

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

Исполнитель работает только с натуральными числами.

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

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

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

вычти 2

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

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

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

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

11221

Пояснение

Решение.

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

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $144$ к исходному числу $2$ . При этом команды будут инвертированы (обратны):
1. Вместо возведения в квадрат будем извлекать квадратный корень: $\sqrt{x}$ .
2. Вместо вычитания двойки будем её прибавлять: $x + 2$ .

Шаг 1. Посмотрим на число $144$ . Оно является полным квадратом ( $12^2 = 144$ ). Значит, последней командой в прямом алгоритме (из $2$ в $144$ ) логично предположить возведение в квадрат.
Если последняя команда — №1, то на предыдущем шаге было число $\sqrt{144} = 12$ .

Шаг 2. Теперь работаем с числом $12$ . Является ли оно квадратом натурального числа? Нет ( $\sqrt{12}$ — не целое число). Значит, к числу $12$ мы могли прийти только с помощью команды №2 (вычти 2).
В обратном ходе прибавляем: $12 + 2 = 14$ .

Шаг 3. Работаем с числом $14$ . Оно также не является полным квадратом. Значит, снова используем обратную команду для №2.
Прибавляем: $14 + 2 = 16$ .

Шаг 4. Число $16$ является полным квадратом ( $4^2 = 16$ ). Значит, в прямом алгоритме здесь могла быть команда №1.
В обратном ходе извлекаем корень: $\sqrt{16} = 4$ .

Шаг 5. Число $4$ является полным квадратом ( $2^2 = 4$ ).
В обратном ходе извлекаем корень: $\sqrt{4} = 2$ . Мы пришли к исходному числу!

Теперь запишем наши действия в прямом порядке (от $2$ к $144$ ):
1. Число $2$ . Команда 1 (возведи в квадрат): $2^2 = 4$ .
2. Число $4$ . Команда 1 (возведи в квадрат): $4^2 = 16$ .
3. Число $16$ . Команда 2 (вычти 2): $16 - 2 = 14$ .
4. Число $14$ . Команда 2 (вычти 2): $14 - 2 = 12$ .
5. Число $12$ . Команда 1 (возведи в квадрат): $12^2 = 144$ .

Полученная последовательность команд: 11221. Она содержит ровно 5 команд, что соответствует условию задачи.

Ответ: 11221

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