Алгоритм получает на вход натуральное число N > 1 и строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. Подсчитывается количество нулей и единиц в полученной записи. Если их количество одинаково, в конец записи добавляется её последняя цифра. В противном случае в конец записи добавляется та цифра, которая встречается реже.
3. Шаг 2 повторяется ещё два раза
4. Результат переводится в десятичную систему.
Пример. Дано число N = 19. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 10011.
2. В полученной записи нулей меньше, чем единиц, в конец записи добавляется 0. Новая запись: 100110.
3. В текущей записи нулей и единиц поровну, в конец записывается последняя цифра,
4. Результат работы алгоритма R = 153.
При каком наименьшем числе N > 99 в результате работы алгоритма получится число,
Заметим, что чтобы число было кратно четырём, его двоичная запись должна оканчиваться
Число на выходе должно превышать 9910 = 11000112. Рассмотрим числа N, большие или равные 100, и определим наименьшее из них, при котором результат на экране автомата будет кратным 4.
10010 = 11001002, результатом работы алгоритма будет число 11001001102, что не кратно 4.
10110 = 11001012, результатом работы алгоритма будет число 11001010012, что не кратно 4.
10210 = 11001102, результатом работы алгоритма будет число 11001100012, что не кратно 4.
10310 = 11001112, результатом работы алгоритма будет число 11001110002, что подходит под условие кратности 4.
Таким образом, ответ — 103.
Ответ: 103.
Приведём другое решение на языке Python.
for n in range(100, 1000):
s = bin(n)[2:] # перевод в двоичную систему
for i in range(3):
if s.count("1") == s.count("0"):
s += s[-1]
elif s.count("1") > s.count("0"):
s += "0"
else:
s += "1"
r = int(s, 2) # перевод в десятичную систему
if r % 4 == 0:
print(n)
break