Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1101.
2. Сумма цифр двоичной записи — 3, остаток от деления
3. Сумма цифр полученной записи — 4, остаток от деления
4. На экран выводится число 54.
Какое наименьшее число, большее 97, может появиться на экране в результате работы автомата?
Рассмотрим числа,
98 = 11000102 — не является результатом работы алгоритма.
99 = 11000112 — не является результатом работы алгоритма.
100 = 11001002 — не является результатом работы алгоритма.
101 = 11001012 — не является результатом работы алгоритма.
102 = 11001102 — является результатом работы алгоритма для числа 11001.
Ответ: 102.
Приведём другое решение на языке Python.
def f(s):
summa = 0
for i in range(len(s)):
summa += int(s[i])
return summa
for n in range(1, 100):
s = bin(n)[2:] # перевод в двоичную систему
summa = f(s)
s = s + str(summa % 2)
summa = f(s)
s = s + str(summa % 2)
r = int(s, 2) # перевод в десятичную систему
if r > 97:
print(r)
break
Приведём решение Ильи Волкова на языке Python.
for n in range (1,1001):
b = bin(n)[2:]
b += str(b.count('1') % 2)
b += str(b.count('1') % 2)
r = int(b,2)
if r > 97:
print(r)
break