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

Решение.

Нам необходимо составить алгоритм получения из числа $4$ числа $58$, используя не более 5 команд. Доступны две команды: 1) прибавь 3; 2) возведи в квадрат.

Для решения таких задач удобнее всего двигаться «с конца» — от итогового числа $58$ к исходному числу $4$. При этом команды заменяются на обратные: вместо «прибавь 3» мы будем «вычитать 3», а вместо «возведи в квадрат» — «извлекать квадратный корень».

Шаг 1. Посмотрим на число $58$. Из него нельзя извлечь целый квадратный корень, значит, последней командой точно было прибавление 3. Выполним обратное действие: $58 - 3 = 55$. (Команда 1)

Шаг 2. Из числа $55$ также нельзя извлечь корень. Снова вычитаем 3: $55 - 3 = 52$. (Команда 1)

Шаг 3. Из числа $52$ корень не извлекается. Вычитаем 3: $52 - 3 = 49$. (Команда 1)

Шаг 4. Число $49$ является полным квадратом ($7^2 = 49$). Значит, на этом этапе мы могли применить команду возведения в квадрат. Выполним обратное действие — извлечение корня: $\sqrt{49} = 7$. (Команда 2)

Шаг 5. Из числа $7$ вычитаем 3: $7 - 3 = 4$. (Команда 1). Мы пришли к исходному числу $4$.

Теперь запишем последовательность команд в прямом порядке (от $4$ к $58$):
1. Число $4$. Применяем команду 1: $4 + 3 = 7$.
2. Число $7$. Применяем команду 2: $7^2 = 49$.
3. Число $49$. Применяем команду 1: $49 + 3 = 52$.
4. Число $52$. Применяем команду 1: $52 + 3 = 55$.
5. Число $55$. Применяем команду 1: $55 + 3 = 58$.

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

Ответ: 12111

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