Задача к ЕГЭ по информатике на тему «Запись числа в двоичной системе счисления» №2

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

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

2. К этой записи дописывается единица.

3. Затем справа дописывается бит чётности: $0$ , если в двоичном коде полученного числа чётное число единиц, и $1$ , если нечётное.

4. К полученному результату дописывается ещё один бит чётности.

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

for n in range(1, 100):
    s = bin(n)[2:]  # перевод в двоичную систему
    s = str(s)
    s += ’1’
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    r = int(s, 2)  # перевод в десятичную систему
    if r > 168:
        print(r)
        break

Аналитическое решение:

Имеется число $N$ . В любом случае к нему дописывается единица, поэтому будем рассуждать, будто бы число и было таким(с дописанной единицей) изначально. Если количество единиц чётно, то и сумма цифр числа чётна, а значит к числу допишется ноль. Если же количество единиц нечётно, то и сумма цифр числа нечётна, а значит к числу допишется единица. Если мы дописали единичку, то количество единиц увеличится на 1, а значит, что после этого сумма будет чётна, и уже в следующем пункте мы допишем нолик. Если мы дописали ноль, то сумма числа не меняется, а значит в следующем пункте мы также допишем нолик. Значит число в 2 СС заканчивается на 100 или 110 (учли, что мы изначально при любых обстоятельствах дописываем единицу, а потом 00 или 10).

Нам необходимо найти число, большее, чем 168, которое в 2 СС заканчивается на 100 или 110. Будем перебирать с минимального.

Подойдет ли число $16910 = 101010012$ ? Нет, оно кончается на 001.

Подойдет ли число $170 = 10101010 10 2$ ? Нет, оно кончается на 010.

Подойдет ли число $17110 = 101010112$ ? Нет, оно кончается на 011.

Подойдет ли число $17210 = 101011002$ ? Да, так как оно заканчивается на 100. Значит это и есть наш ответ.

Ответ: 172