Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 19
Условие
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью результирующего числа R.
Укажите такое наименьшее число N, для которого результат работы алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Подсказки — как подойти к решению
- Разберись, как связаны исходное число и результат: дописывание двух разрядов превращает запись в учетверённую исходную с небольшой добавкой. Определи, чему равны эти два случая.
- Ищи наименьший результат, больший заданного числа, а затем восстанови из него исходное делением — но обязательно проверь, согласуется ли остаток с правилом и совпадает ли количество единиц в исходной записи с тем, что было дописано.
- Если число не прошло проверку, переходи к следующему: удобно писать короткий перебор по исходным числам и останавливаться на первом, чей результат превысил границу. В ответ идёт исходное число, а не результат работы алгоритма.
Решение
Если изначально сумма разрядов была чётная, то в конец запишется 00, что эквивалентно N arrow N умножить на 4.
Если же сумма была нечётная, то запишется 10, что эквивалентно N arrow N умножить на 4 плюс 2.
В обоих случаях число получается чётным.
Посмотрим на чётные числа, превосходящие 77.
78_10 = 1001110_2 — на конце 10, а сумма остальных разрядов нечётна. Число подходит под второй случай, значит, число, из которого оно было получено, равно дробь: числитель: 78 минус 2, знаменатель: 4 конец дроби = 19.
Ответ: 19.
Приведём другое решение на языке 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)
s = s + str(f(s) % 2)
s = s + str(f(s) % 2)
r = int(s, 2) # перевод в десятичную систему
if r > 77:
print(n)
break
Приведём решение Глеба Придатько на языке Python.
for n in range(50):
r = bin(n)[2:]
r += str(r.count('1') % 2)
r += str(r.count('1') % 2)
if int(r, 2) > 77:
print(n)
break
Типичные ошибки
- Взято подходящее число, но не наименьшее из возможных: проверку прошло и меньшее значение. Перебирай исходные числа по возрастанию и останавливайся на первом успешном.
- В ответ попало значение результата, а вопрос был про исходное число. Перечитай формулировку: записать нужно то, что подаётся на вход алгоритма.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике