Разбор задания ОГЭ по информатике. Март 2025. Простой линейный алгоритм для формального исполнителя. Получение большего числа из меньшего

Тип 5 № 16013

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

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

2.  прибавь 3

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

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

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

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

прибавь 3

прибавь 3

прибавь 3

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

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

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

Решение.

Не любое число является квадратом целого числа, поэтому, если мы пойдем от числа 25 к числу 1, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.

Число 25 является квадратом. Если образовали его, пользуясь первой командой (25  =  5 · 5), то предшествующим являлось число 5. Число 5 с помощью второй команды получилось из числа 2, к которой дойти от 1, используя данные команды, невозможно.

1.  Значит, 25 было получено добавлением трех к числу 22: 22 + 3 = 25 (команда 2).

2.  Число 22 не является квадратом, поэтому оно получено добавлением трех к числу 19: 19 + 3 = 22 (команда 2).

3.  Число 19 не является квадратом, поэтому оно получено добавлением трех к числу 16: 19 = 16 + 3 (команда 2).

4.  Число 16 является квадратом числа 4: 16 = 4 · 4 (команда 1).

5.  Число 4 можно получить возведением в квадрат числа 2 (команда 1) либо прибавлением 3 к числу 1 (команда 2). Поскольку исходным должно быть число 1, а в программе должно быть не более пяти команд, выбираем второй вариант: 4 = 1 + 3 (команда 2).

Искомая последовательность команд: 21222.

Ответ: 21222.

Приведем другое решение.

Возводить число 1 в квадрат бесполезно, поскольку все равно получится 1. Значит, сначала используем команду 2 («прибавь 3»). При этом получится число 4. Если использовать команду 2 («прибавь 3») еще раз, то получим число 7, которое при возведении в квадрат даст больше 25. Поэтому используем команду 1 («возведи в квадрат»), получим число 16. Теперь три раза используем команду 2 («прибавь 3»), и получим 16 + 3 + 3 + 3  =  25. Следовательно, последовательность команд 21222.

Приведем другое решение на языке Python.

def f(flag, x): if flag == 1: return x**2 if flag == 2: return x + 3   x = 1 for flag in range(1, 3): for flag1 in range(1, 3): for flag2 in range(1, 3): for flag3 in range(1, 3): for flag4 in range(1, 3): if f(flag, f(flag1, f(flag2, f(flag3, f(flag4, x))))) == 25: print(flag4, flag3, flag2, flag1, flag)

Источник: ОГЭ по информатике 2020. Досрочная волна. Вариант 1