Задачи ЕГЭ-5. Алгоритмы обработки чисел (двоичные числа). Классная работа

Задача 1.

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число следующим образом:

1. Строится двоичная запись числа N

2. К этой записи дописывается справа бит чётности: 0, если в двоичном коде числа N было чётное число единиц, и 1, если нечётное.

3. Полученное число переводится в десятичную систему счисления.

Какое число получится, если на вход было подано число 19?

Способ 1

Используем графическую схему алгоритма

Ответ: 39

Способ 2

Для перевода числа из десятичной системы счисления в двоичную можно воспользоваться оператором bin(). В качестве аргумента нужно передать значение в виде числа, а оператор вернет строку с двоичным числом. У результата также будет префикс 0b, указывающий на основание системы счисления.

a=bin(19)
print(a)
print(1*2**5+0*2**4+0*2**3+1*2**2+1*2**1+1*2**0)

0b10011

39

Способ 3

Для обратного перевода в десятичную систему счисления мы будем использовать оператор int(). Для этого передадим ему два аргумента, первый - это строка с числом в какой-то системе счисления, а второй - это основание системы счисления самого числа. По умолчанию для этого необязательного аргумента стоит значение равное 10.
В качестве самого числа нужно обязательно передать строку. Строка может содержать или само число или число с префиксом системы счисления.

a=bin(19)

print(a)
print(int(a[2:]+'1',2))

39

Здесь бит чётности мы определяли «вручную».

Вопрос: можно ли в задаче подобного типа определить бит чётности в программе автоматически, для любого числа N?

Определим количество «1» в двоичной записи числа N, и остаток от деления суммы на 2 (это «0» или «1») допишем в конец числа (справа).

b=int(input())
a=bin(b)
if a[2:].count('1')%2==0:
print(int(a[2:]+'0',2))

else:
print(int(a[2:] + '1', 2))

или:

a=bin(int(input()))
if a[2:].count('1')%2==0:
print(int(a[2:]+'0',2))
else:
print(int(a[2:] + '1', 2))

Задача 2.

На вход алгоритма подается натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N

2. К этой записи дописываются справа еще два разряда по следующему правилу:

   • складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

   • над этой записью производятся те же действия — справа дописывается остаток от деления суммы ее цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите такое наибольшее число N, для которого результат работы данного алгоритма будет меньше значения 86. В ответе это число запишите в десятичной системе счисления.

Предварительный анализ алгоритма показывает, что описанный алгоритм представляет собой классический бит чётности, добавленный дважды.

Способ 1

Используем графическую схему алгоритма

Так как заданным является результат, будем идти по схеме «задом наперёд», перебирая числа, меньшие 86:

Способ 2.

Перебираем в цикле числа от 85 до 1 с шагом -1, затем в срезе строки с двоичным кодом без двух первых и двух последних цифр считаем бит чётности, если он совпадает предпоследней цифрой, то проверяем бит чётности в срезе строки без одной последней цифры. При выполнении обоих условий выводим найденное число в десятичной системе счисления.

for r in range(85, 1,-1):
a=bin(r)
print(a[2:-2])
if a[2:-3].count('1')%2==a[:-2] and a[2:-2].count('1')%2==a[:-1]:
print(int(a[2:-2],2))