Задание №5 ЕГЭ Информатика с ответом и решением
Ответ: 115
Условие
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу: складываются все цифры двоичной записи:
а) если сумма нечетная, к числу дописывается 11,
б) если сумма четная, дописывается 00.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число R, которое превышает 114 и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.
Подсказки — как подойти к решению
- Определи, какие два разряда дописываются в каждом из случаев, и что это означает для результата: дописывание двух нулей равносильно умножению на четыре, а двух единиц — добавлению к учетверённому числу ещё трёх.
- Отсюда вывод: результат работы алгоритма — не любое число, а только такое, чей хвост согласован с чётностью суммы цифр исходной записи. Проверяй числа, начиная с ближайшего большего за границей, и отбрасывай те, у которых хвост не подходит.
- Можно идти и обратным путём: отбрось у проверяемого числа два последних разряда, посчитай количество единиц в оставшейся записи и убедись, что дописанные разряды действительно такие. Первое подошедшее число и запиши в ответ.
Решение
Переведем число 11410 в двоичную систему: 11410 = 111 00102. Отсюда узнаем число на входе — 111002. Следуя алгоритму, нужно проверить четность единиц. Количество единиц нечетно, следовательно, нужно добавить две единицы. Получаем число 115, оно и является ответом, так как оно больше 114 и наименьшее из возможных.
Ответ: 115.
Приведём другое решение на языке Python.
for n in range(1, 100):
summa = 0
s = bin(n)[2:] # перевод в двоичную систему
s = str(s)
for i in range(len(s)):
summa += int(s[i])
if summa % 2 != 0:
s += "11"
else:
s += "00"
r = int(s, 2) # перевод в десятичную систему
if r > 114:
print(r)
break
Приведём другое решение на языке Python.
for n in range(1,1000):
r = bin(n)[2:]
r += "11" if (r.count("1") % 2 == 1) else "00"
if (int(r,2)) > 114:
print(int(r,2))
break
Приведём решение Сергея Донец на языке PascalABC.NET.
uses School;
begin
for var i:=1 to 114 do
begin
var b:=bin(i);
var n:=b.CountOf('1');
if n.IsEven
then b+='00'
else b+='11';
var r:=Dec(b,2);
if r>114 then begin
Println(r);halt;end;
end;
end.
Типичные ошибки
- Это число из условия, а не превосходящее его: вопрос требует строго больше заданного. Перечитай границу и начни проверку со следующего числа.
- Число подходит под правило, но оно не наименьшее: между границей и ним есть ещё одно подходящее значение. Продолжай проверку, пока не найдёшь самое первое подходящее.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №5 по информатике