Задание 5 КЕГЭ (автомат с двоичной записью): как не запутаться в порядке действий?
В задании 5 автомат получает число, переводит его в двоичную (или другую) запись, что-то делает с разрядами (складывает, дописывает), и надо найти наименьшее число, для которого результат больше N. Я путаюсь в последовательности шагов автомата и теряю числа. Как решать аккуратно?
2 ответа
Лучший способ для задания 5 — не считать руками, а написать функцию-автомат на питоне ровно по описанию, и перебрать числа.
Типовая структура автомата: перевести в двоичную, посчитать что-то по разрядам, может дописать бит, получить результат. Например, "автомат складывает разряды, и если сумма чётная — дописывает 0, иначе 1":
def avtomat(n):
b = bin(n)[2:] # двоичная запись без '0b'
s = sum(int(c) for c in b)
b = b + ('0' if s % 2 == 0 else '1')
return int(b, 2) # обратно в десятичное
N = 200
for n in range(1, 10000):
if avtomat(n) > N:
print(n)
break
Главное — переписать описание автомата дословно, шаг за шагом, ничего не упуская. Перебор range и break находят наименьшее автоматически. Если решаешь руками — выписывай каждый шаг отдельной строкой на черновике, не пытайся держать в голове.
Если на экзамене паника и код не пишется — реши руками для маленьких чисел и поищи закономерность. Часто результат автомата монотонно растёт с числом, и можно прикинуть, около какого n результат перевалит за N, а потом проверить пару кандидатов точно. Но код надёжнее: автомат легко путается в порядке "сначала перевести, потом дописать" против "дописать, потом перевести".