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

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

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

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

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

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

2. вычти 5

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

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

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

вычти 5

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

вычти 5

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

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

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

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

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

21221

Пояснение

Решение. Для решения этой задачи нам нужно найти последовательность из не более чем 5 команд, которая превратит число $1$ в число $36$ . У нас есть две команды: 1 (возведение в квадрат) и 2 (вычитание 5).

Попробуем рассуждать методом «от обратного» — это часто быстрее. Будем идти от конечного числа $36$ к начальному числу $1$ . При этом команды будут обратными: вместо «возведи в квадрат» — «извлеки корень», вместо «вычти 5» — «прибавь 5».

Шаг 1. Последнее число — $36$ . Как мы могли его получить?
Вариант А: Извлечь корень. $\sqrt{36} = 6$ . (Это соответствует команде 1 в прямом порядке).
Вариант Б: Прибавить 5. $36 + 5 = 41$ . (Это соответствует команде 2 в прямом порядке).

Шаг 2. Рассмотрим вариант А (число $6$ ). Как получить $6$ ?
Вариант А1: Извлечь корень. $\sqrt{6}$ — не целое число, этот путь нам не подходит.
Вариант А2: Прибавить 5. $6 + 5 = 11$ . (Команда 2).

Шаг 3. Рассмотрим число $11$ .
Вариант А2.1: Извлечь корень. $\sqrt{11}$ — не целое число.
Вариант А2.2: Прибавить 5. $11 + 5 = 16$ . (Команда 2).

Шаг 4. Рассмотрим число $16$ .
Вариант А2.2.1: Извлечь корень. $\sqrt{16} = 4$ . (Команда 1).
Вариант А2.2.2: Прибавить 5. $16 + 5 = 21$ .

Шаг 5. Рассмотрим число $4$ .
Вариант А2.2.1.1: Извлечь корень. $\sqrt{4} = 2$ .
Вариант А2.2.1.2: Прибавить 5. $4 + 5 = 9$ .
Стоп, нам нужно прийти к числу $1$ . Давайте проверим путь через число $6$ , который мы начали:
Если мы возьмём число $6$ и прибавим к нему $5$ три раза, мы получим $21$ , что далеко от $1$ . Попробуем другой путь.

Давайте проверим прямым ходом последовательность 21221, указанную в условии как правильную:
1. Начальное число: $1$ .
2. Команда 2 (вычти 5): $1 - 5 = -4$ .
3. Команда 1 (возведи в квадрат): $(-4)^{2} = 16$ .
4. Команда 2 (вычти 5): $16 - 5 = 11$ .
5. Команда 2 (вычти 5): $11 - 5 = 6$ .
6. Команда 1 (возведи в квадрат): $6^{2} = 36$ .

Проверка:
$1 \xrightarrow{2} -4 \xrightarrow{1} 16 \xrightarrow{2} 11 \xrightarrow{2} 6 \xrightarrow{1} 36$ .
Алгоритм состоит из 5 команд, что соответствует условию задачи.

Ответ: 21221

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