Алгоритм получает на вход натуральное число > 1 и строит по нему новое число следующим образом:
-
Строится двоичная запись числа .
-
Вычисляется количество единиц, стоящих на чётных местах в двоичной записи числа без ведущих нулей, и количество нулей, стоящих на нечётных местах. Места отсчитываются слева направо (от старших разрядов к младшим, начиная с единицы).
-
Результатом работы алгоритма становится модуль разности полученных двух чисел.
Пример. Дано число = 39. Алгоритм работает следующим образом:
-
Строится двоичная запись: 3910 = 1001112.
-
Выделяем единицы на чётных и нули на нечётных местах: 100111. На чётных местах стоят две единицы, на нечётных – один ноль.
-
Модуль разности равен 1.
Результат работы алгоритма = 1.
При каком наименьшем в результате работы алгоритма получится = 4?
Решение:
Решение на Python:
otv = []
for N in range(2, 100000):
s = bin(N)[2:]
a = s[1::2].count('1')
b = s[::2].count('0')
R = abs(a - b)
if R == 4:
otv.append(N)
print(min(otv))Ответ: 255