Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 46
Условие
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите минимальное число R, которое превышает 43 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Подсказки — как подойти к решению
- Разберись, что именно дописывается справа: сначала остаток от деления суммы цифр на 2, затем — снова остаток, но уже для удлинённой записи. Посмотри, какие две последние цифры вообще могут появиться у результата.
- Полезное наблюдение: дописанные разряды определяются чётностью количества единиц, поэтому хвост результата всегда один из двух вариантов, а само число всегда чётное. Значит, не любое число может получиться в результате работы алгоритма.
- Проверяй числа по возрастанию от заданной границы: переведи число в двоичную запись и проверь, согласуются ли два последних разряда с правилом (второй остаток считается уже с учётом первого дописанного разряда). Первое подходящее число и будет ответом.
Решение
Если в числе было нечётное количество единиц, то в конец допишется 10. Если количество единиц чётное, то допишется 00. Рассмотрим числа, большие 43. Имеем:
4410 = 1011002 — не может являться результатом работы алгоритма;
4510 = 1011012 — не может являться результатом работы алгоритма;
4610 = 1011102 — может являться результатом работы алгоритма, количество единиц (кроме последних двух разрядов) нечетное, и в последних двух разрядах 10.
Ответ: 46.
Приведём другое решение на языке 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:] # перевод в двоичную систему
s = str(s)
summa = f(s)
s = s + str(summa % 2)
summa = f(s)
s = s + str(summa % 2)
r = int(s, 2) # перевод в десятичную систему
if r > 43:
print(r)
break
Приведём решение Демида Мишукова на языке Python.
for n in range (1,100):
s = bin(n)[2:]
if s.count('1') % 2 == 0:
s += '00'
else:
s += '10'
r = int(s,2)
if r>43:
print(r)
break
Приведём решение Михаила Глинского на языке Python.
for N in range(100):
s = bin(N)[2:]
k = s.count('1')
s = s + str(k % 2)
k = s.count('1')
s = s + str(k % 2)
R = int(s,2)
if R > 43:
print(R)
break
Приведём решение Матвея Ахтямова на языке Python.
r = []
for n in range(1,1000):
s = bin(n)[2:]
a = s + (str(sum([int(i) for i in str(s)])%2))
b = a + (str(sum([int(i2) for i2 in str(a)])%2))
if int(b,2) > 43:
r.append(int(b,2))
print(min(r))
Приведём решение Алексея Долгова на языке Python.
for i in range (1,100):
r = i << 2
if i % 2 != 0:
r += 2
if r > 43:
print(r)
break
Типичные ошибки
- Число взято просто как ближайшее большее, без проверки: у него такой хвост, который алгоритм получить не может. Восстанавливай исходную запись и сверяй её с последними двумя разрядами.
- Соседнее число тоже не является результатом работы алгоритма: его последние разряды не соответствуют остаткам от деления суммы цифр на 2. Проверяй числа подряд, пока не найдёшь действительно подходящее.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике