Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 102
Условие
Автомат обрабатывает натуральное число N по следующему алгоритму.
1. Строится двоичная запись числа N.
2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
3. Предыдущий пункт повторяется для записи с добавленной цифрой.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом.
1. Двоичная запись числа N: 1101.
2. Сумма цифр двоичной записи — 3, остаток от деления на 2 равен 1, новая запись 11011.
3. Сумма цифр полученной записи — 4, остаток от деления на 2 равен 0, новая запись 110110.
4. На экран выводится число 54.
Какое наименьшее число, большее 97, может появиться на экране в результате работы автомата?
Подсказки — как подойти к решению
- Обрати внимание: разряд дописывается дважды, причём второй раз сумма считается уже по удлинённой записи. Проследи по примеру из условия, как при этом меняется чётность.
- Из-за двукратного дописывания у результата не любой хвост: проверяй числа по возрастанию от заданной границы и восстанавливай исходную запись, поочерёдно отбрасывая разряды с конца и сверяя каждый шаг с правилом.
- Надёжнее всего написать короткий перебор: для чисел от единицы до нескольких сотен построй запись, дважды допиши остаток от деления суммы цифр на 2 и переведи результат в десятичную систему. Остановись на первом результате, который больше заданного числа.
Решение
Рассмотрим числа, большие 97, и найдем меньшее число, которое является результатом работы алгоритма.
98 = 11000102 — не является результатом работы алгоритма.
99 = 11000112 — не является результатом работы алгоритма.
100 = 11001002 — не является результатом работы алгоритма.
101 = 11001012 — не является результатом работы алгоритма.
102 = 11001102 — является результатом работы алгоритма для числа 11001.
Ответ: 102.
Приведём другое решение на языке Python.
def f(s):
summa = 0
for i in range(len(s)):
summa += int(s[i])
return summa
for n in range(1, 100):
s = bin(n)[2:] # перевод в двоичную систему
summa = f(s)
s = s + str(summa % 2)
summa = f(s)
s = s + str(summa % 2)
r = int(s, 2) # перевод в десятичную систему
if r > 97:
print(r)
break
Приведём решение Ильи Волкова на языке Python.
for n in range (1,1001):
b = bin(n)[2:]
b += str(b.count('1') % 2)
b += str(b.count('1') % 2)
r = int(b,2)
if r > 97:
print(r)
break
Типичные ошибки
- Взято первое число после границы без проверки: по правилу оно не восстанавливается. Пропускай числа, которые алгоритм получить не может.
- У этого числа последние разряды не согласуются с остатками от деления суммы цифр на 2. Проверяй кандидата «обратным ходом»: отбрось два разряда и посчитай сумму заново.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике