Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 101
Условие
Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу: если N чётное, в конец числа (справа) дописывается 10, в противном случае справа дописывается
01. Например, двоичная запись 1001 числа 9 будет преобразована в 100101.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью числа — результата работы данного алгоритма.
Укажите максимальное число R, которое не превышает 102 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.
Подсказки — как подойти к решению
- Разберись с правилом дописывания: у чётного числа хвост один, у нечётного — другой. Отсюда следует, что результат связан с исходным числом умножением на четыре плюс небольшая добавка.
- Проверяй числа от заданной границы вниз: первое, у которого последние два разряда подходят под правило, нужно ещё проверить «обратным ходом» — совпадает ли чётность восстановленного числа с видом хвоста.
- Если считать вручную долго, напиши перебор: для чисел от единицы до сотни построй запись, допиши два разряда по чётности числа и переведи результат в десятичную систему, а затем выбери наибольший результат, не превышающий границу.
Решение
Рассмотрим числа, не превышающие 102, и найдем максимальное число, которое является результатом работы алгоритма.
10210 = 11001102 — не может являться результатом работы алгоритма.
10110 = 11001012 — является результатом работы алгоритма.
Ответ: 101.
Приведём другое решение на языке Python.
for n in range(100, 1, -1):
s = bin(n)[2:] # перевод в двоичную систему
if n % 2 == 0:
s += "10"
else:
s += "01"
r = int(s, 2) # перевод в десятичную систему
if r <= 102:
print(r)
break
Типичные ошибки
- Взято первое проверяемое число, хотя результатом работы алгоритма оно быть не может: хвост не согласуется с чётностью исходного числа. Отбрасывай кандидатов, пока обратная проверка не сойдётся.
- У этого числа хвост тоже не подходит под правило дописывания. Проверяй последние два разряда и восстанавливай исходное число — так сразу видно, возможен ли такой результат.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике