Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. Если число N четное, то в конец записи числа (справа) дописывается 1, если N нечетное то 0.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 17. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 10001.
2. N не четное, поэтому в конец дописывается 0, новая запись 100010.
3. 100010 четное поэтому в конец дописывается 1, новая запись 1000101.
4. На экран выводится число 69.
Какое наибольшее число, меньше 109, может появиться на экране в результате работы автомата?
mx = 0
for n in range(1, 1000):
b = bin(n)[2:]
for i in range(2):
if b[-1] == ’0’:
b += ’1’
else:
b += ’0’
r = int(b, 2)
if r < 109:
mx = max(mx, r)
print(mx)
Ответ: 106