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

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

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

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

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

1. вычти 1

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

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

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

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

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

вычти 1

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

вычти 1,

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

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

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

21212

Пояснение

Решение.

Нам необходимо составить алгоритм для исполнителя «Квадратор», который преобразует число $2$ в число $64$ ровно за $5$ команд. Доступны две операции:
1. «вычти 1»
2. «возведи в квадрат»

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $64$ к исходному числу $2$ . При движении в обратном направлении команды меняются на противоположные:
1. Вместо «вычти 1» будем выполнять «прибавь 1».
2. Вместо «возведи в квадрат» будем выполнять «извлеки квадратный корень» (это возможно только если число является полным квадратом).

Шаг 1. Начнём с числа $64$ .
Из числа $64$ можно извлечь корень: $\sqrt{64} = 8$ . Это команда 2 (в обратном порядке).
Если бы мы прибавляли 1, получили бы $65$ , из которого корень не извлекается, и мы бы быстро превысили лимит команд.

Шаг 2. Теперь у нас число $8$ .
Из числа $8$ корень не извлекается. Значит, единственный путь в обратном направлении — прибавить 1.
$8 + 1 = 9$ . Это команда 1 (в обратном порядке).

Шаг 3. Теперь у нас число $9$ .
Из числа $9$ можно извлечь корень: $\sqrt{9} = 3$ . Это команда 2 (в обратном порядке).

Шаг 4. Теперь у нас число $3$ .
Из числа $3$ корень не извлекается. Прибавляем 1.
$3 + 1 = 4$ . Это команда 1 (в обратном порядке).

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

Запишем полученные команды в обратном порядке (от начала к концу):
1. Число $2$ . Возводим в квадрат (команда 2) $\rightarrow 4$ .
2. Число $4$ . Вычитаем 1 (команда 1) $\rightarrow 3$ .
3. Число $3$ . Возводим в квадрат (команда 2) $\rightarrow 9$ .
4. Число $9$ . Вычитаем 1 (команда 1) $\rightarrow 8$ .
5. Число $8$ . Возводим в квадрат (команда 2) $\rightarrow 64$ .

Последовательность команд: $21212$ .

Ответ: 21212

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