На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма
ИЛИ
У исполнителя Калькулятор две команды, которым присвоены номера:
1. прибавь 2,
2. умножь на 5.
Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5.
Например, программа 2121 — это программа
умножь на 5,
прибавь 2,
умножь на 5,
прибавь 2,
которая преобразует число 1 в число 37.
Запишите порядок команд в программе, которая преобразует число 2 в число 24 и содержит не более четырёх команд. Указывайте лишь номера команд.
Данный алгоритм приписывает в конце числа
12610 = 11111102 может получиться в результате работы алгоритма из числа 111112.
111112 = 3110.
Ответ: 31.
Приведём другое решение на языке Python.
for n in range(2, 100): # начинаем с 2, так как число 1 имеет только одну цифру
s = bin(n)[2:] # перевод в двоичную систему
s = str(s)
s += str(s.count("1") % 2)
s += str(s.count("1") % 2)
r = int(s, 2) # перевод в десятичную систему
if r > 125:
print(n)
break
ИЛИ
Решим задачу от обратного, а потом запишем полученные команды справа налево. Если число не делится на 5, тогда получено через команду 1, если делится, то через команду 2. Вычислим:
22 + 2 = 24 (команда 1);
20 + 2 = 22 (команда 1);
4 · 5 = 20 (команда 2);
2 + 2 = 4 (команда 1).
Ответ: 1211.

