Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 1009
Условие
Автомат обрабатывает натуральное число N > 1 по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Последняя цифра двоичной записи удаляется.
3. Если исходное число N было нечётным, в конец записи (справа) дописываются цифры 10, если чётным — 01.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1101.
2. Удаляется последняя цифра, новая запись: 110.
3. Исходное число нечётно, дописываются цифры 10, новая запись: 11010.
4. На экран выводится число 26.
Какое число нужно ввести в автомат, чтобы в результате получилось 2018?
Подсказки — как подойти к решению
- Работай от результата к исходному: переведи результат в двоичную запись и вспомни, что у исходного числа автомат удалил один разряд, а вместо него приписал два. Чётность исходного числа определяется по хвосту записи.
- Для нечётного числа удаление последней цифры и дописывание пары «один, ноль» равносильно дописыванию нуля. Значит, восстановление сводится к отбрасыванию одной последней двоичной цифры результата — и обязательно проверь чётность полученного числа.
Решение
Переведём число 201810 в двоичную систему счисления: 111 1110 00102. Удалим последние 2 цифры двоичной записи числа 2018. Заметим, что число должно быть нечётным, поскольку последние 2 цифры двоичной записи числа 2018 равняются 10. Значит, искомое число — 11 1111 00012 = 100910.
Ответ: 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)
Типичные ошибки
- Похоже, ты отбросил у результата сразу два последних разряда: автомат удалял только один разряд исходного числа, второй добавленный разряд остаётся. Отбрасывай ровно одну последнюю двоичную цифру.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике