Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 126
Условие
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1) Строится двоичная запись числа N.
2) К этой записи дописываются справа ещё два разряда по следующему правилу:
а) находится остаток от деления на 2 суммы двоичных разрядов N, полученный результат дописывается в конец двоичной последовательности N.
б) пункт а повторяется для вновь полученной последовательности.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите минимальное число R, которое превышает 123 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе.
Подсказки — как подойти к решению
- Разберись с правилом: дописывается не цифра числа, а остаток от деления суммы всех разрядов на два, причём перед вторым дописыванием сумму нужно посчитать заново — уже вместе с добавленной цифрой.
- Иди по кандидатам от порога вверх: переводи число в двоичную запись и проверяй, можно ли получить её из более короткой по этому правилу. Первое подходящее значение и будет ответом, полный перебор по N здесь тоже работает.
Решение
Рассмотрим числа, большие 123, и найдем минимальное число, которое является результатом работы алгоритма.
12410 = 11111002 — не может являться результатом работы алгоритма.
12510 = 11111012 — не может являться результатом работы алгоритма.
12610 = 11111102 — является результатом работы алгоритма.
Ответ: 126.
Приведём другое решение на языке 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 > 123:
print(r)
break
Приведём другое решение на языке Python.
for n in range(1, 100):
s = bin(n)[2:]
s = s + str(s.count('1') % 2)
s = s + str(s.count('1') % 2)
r = int(s, 2)
if r > 123:
print(r)
break
Типичные ошибки
- Ты взял первое число после порога, не проверив правило. У подходящего числа хвост из двух разрядов должен согласовываться с суммой разрядов оставшейся части, поэтому кандидатов нужно перебирать по порядку.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике