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

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

Автомат обрабатывает натуральное число N по следующему алгоритму:

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

2. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления полученной суммы на $2$ .

3. Предыдущий пункт повторяется для записи с добавленной цифрой.

4. Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число $N = 13$ . Алгоритм работает следующим образом:

1. Двоичная запись числа $N : 1101$ .

2. Сумма цифр двоичной записи $3$ , остаток от деления на $2$ равен $1$ , новая запись $11011$ .

3. Сумма цифр полученной записи $4$ , остаток от деления на $2$ равен $0$ , новая запись $110110$ .

4. На экран выводится число $54$ .

Какое наименьшее число, большее вашего балла на ЕГЭ ( $100$ ), может появится на экране в результате работы автомата?

for i in range(1000000):
    s = bin(i)[2::]
    s += str(s.count(’1’) % 2)
    s += str(s.count(’1’) % 2)
    if int(s, 2) > 100:
        print(int(s, 2))
        break

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

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

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

Подойдет ли число $10110 = 11001012$ ? Нет, оно кончается на 01.

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

Ответ: 102