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

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

Строится двоичная запись числа $N$ .
К этой записи справа дописывается единица.
Затем справа дописывается бит чётности: $0$ , если в двоичном коде полученного числа чётное число единиц, и $1$ , если нечётное.
К полученному результату дописывается ещё один бит чётности.

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

Решение программой:

for i in range(1, 1000000):
    s = bin(i)[2::]
    s += ’1’
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    # второй if не нужен, потому что всегда будет дописываться 0
    # подумайте почему)
    if s.count(’1’) % 2 == 0:
        s += ’0’
    else:
        s += ’1’
    if int(s, 2) > 212:
        print(int(s, 2))
        break

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

Каким бы не было число, на втором шаге к нему всегда дописывается единица, так что давайте называть это число «изначальным».

Если изначальное число $N$ имеет чётное количество единиц, то после добавления нуля количество единиц не изменится, а потому на следующем шаге также добавится ноль. Итого к числу допишут два нуля.

Если изначально число $N$ имеет нечётное количество единиц, то после добавления единицы количество единиц увеличится на $1$ , что означает, что количество единиц станет чётным числом, а значит на следующем шаге уже будут добавлять ноль. Итого к числу допишут единицу и ноль.

Значит мы будем проверять только числа, которые кончаются на $100$ или $110$ .

Могло ли получиться число $213$ ? Нет, в двоичной СС оно выглядит как $110101012$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $214$ ? В двоичной СС оно выглядит как $11010110 2$ . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число $110102$ , добавим к нему единицу и получим число $1101012$ , у него чётное число единиц, а значит после работы алгоритма к нему дописали бы два нуля, но мы откинули $110$ , а значит это не то число, которое нам нужно.

Могло ли получиться число $215$ ? Нет, в двоичной СС оно выглядит как $110101112$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $216$ ? Нет, в двоичной СС оно выглядит как $110110002$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $217$ ? Нет, в двоичной СС оно выглядит как $110110012$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $218$ ? Нет, в двоичной СС оно выглядит как $110110102$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $219$ ? Нет, в двоичной СС оно выглядит как $110110112$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $220$ ? В двоичной СС оно выглядит как $110111002$ . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число $110112$ , добавим к нему единицу и получим число $1101112$ , у него нечётное число единиц, а значит после работы алгоритма к нему дописали бы единицу и ноль, но мы откинули $100$ , а значит это не то число, которое нам нужно.

Могло ли получиться число $221$ ? Нет, в двоичной СС оно выглядит как $110111012$ , а значит получиться после алгоритма не могло.

Могло ли получиться число $222$ ? В двоичной СС оно выглядит как $110111102$ . Так что вполне возможно. Если откинем последние три цифры, то у нас останется число $110112$ , добавим к нему единицу и получим число $1101112$ , у него нечётное число единиц, а значит после работы алгоритма к нему дописали бы единицу и ноль, а мы откинули как раз $110$ , значит $222$ – это интересующее нас число.

Ответ: 222