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

Просмотров 8 Комментарии 0

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

Строится двоичная запись числа $N$ .
К этой записи дописываются ещё два разряда по следующему правилу:
1. cкладываются все цифры двоичной записи числа $N$ , и остаток от деления суммы на $2$ дописывается в конец числа (справа). Например, запись числа $11100$ преобразуется в запись $111001$ ;
2. над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на $2$ .

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

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

Аналитическое решение:
Заметим, что если число единиц в двоичной записи нечётное, то в первый раз допишется единица, а затем число единиц станет чётным, и во второй раз мы допишем ноль. Если же число единиц в двоичной записи чётное, то в первый раз мы допишем ноль, затем количество единиц не изменится, и мы снова допишем ноль. Таким образом, в любом случае последняя цифра числа — ноль. Напишем программу:

for i in range(1, 100):
    s = bin(i)[2::]
    a = 0
    for j in range(len(s)):
        a += int(s[j])
    if a % 2 == 0:
        s += ’00’
    else:
        s += ’10’
    if int(s, 2) > 43:
        print(int(s, 2))
        break

Ответ: 46