У исполнителя Квадратор две команды. которым присвоены номера:
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:
3. Число 19 не является квадратом, поэтому оно получено добавлением трех к числу
4. Число 16 является квадратом числа 4: 16 = 4 · 4 (команда 1).
5. Число 4 можно получить возведением в квадрат числа 2 (команда 1) либо прибавлением 3 к числу 1 (команда 2). Поскольку исходным должно быть число 1, а в программе должно быть не более пяти команд, выбираем второй вариант:
Искомая последовательность команд: 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)