Алгоритм получает на вход натуральное число > 1 и строит по нему новое число следующим образом:
-
Строится двоичная запись числа .
-
Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.
-
Шаг 2 повторяется ещё два раза.
-
Результат переводится в десятичную систему счисления.
Пример. Дано число = 19. Алгоритм работает следующим образом:
-
Двоичная запись числа : 10011.
-
В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.
-
В текущей записи нулей и единиц поровну, в конец записывается последняя цифра, это 0. Получается 1001100. В этой записи единиц меньше, в конец добавляется 1: 10011001.
-
Результат работы алгоритма = 153.
При каком наименьшем исходном числе > 104 в результате работы алгоритма получится число, кратное 4?
Решение:
Решение на Python:
otv = []
for N in range(105, 1000):
R = bin(N)[2:]
for i in range(3):
if R.count('0') == R.count('1'):
R += R[-1]
elif R.count('0') < R.count('1'):
R += '0'
else:
R += '1'
R = int(R, 2)
if R % 4 == 0:
otv.append(N)
print(min(otv))Ответ: 107