Автомат обрабатывает натуральное число N > 1 по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Последняя цифра двоичной записи удаляется.
3. Если исходное число N было нечётным, в конец записи (справа) дописываются цифры 10, если чётным — 01.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1101.
2. Удаляется последняя цифра, новая запись: 110.
3. Исходное число нечётно, дописываются цифры 10, новая запись: 11010.
4. На экран выводится число 26.
Какое число нужно ввести в автомат, чтобы в результате
Переведём число 201810 в двоичную систему счисления: 111 1110 00102. Удалим последние
Ответ: 1009.
Приведем другое решение.
Заметим, что если исходное число нечетное, то последняя цифра в его двоичной записи равна 1. Следовательно, удаление последней цифры и дописывание в конец 10 равносильно дописыванию к исходному числу 0. Если же исходное число было четным, то последняя цифра в его двоичной записи равна 0, и удаление последней цифры и дописывание в конец 01 равносильно дописыванию к исходному числу 1. Таким образом, автомат дописывает к нечетному числу 0 и к четному числу 1. Следовательно, для восстановления исходного числа достаточно удалить последнюю двоичную цифру из получившегося числа: 201810 = 111 1110 00102, после удаления последней цифры получим 11 1111 00012 = 100910. Это число является нечетным, значит, в результате работы автомата к нему действительно будет дописан 0.
Приведём другое решение на языке Python.
for n in range(2, 10000):
s = bin(n)[2:] # перевод в двоичную систему
s = str(s)
s = s[:-1]
if n % 2 != 0:
s += "10"
else:
s += "01"
r = int(s, 2) # перевод в десятичную систему
if r == 2018:
print(n)

