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

Алгоритм получает на вход натуральное число 1 » class=»math» src=»/images/inform/quest/quest-3232-1.svg» width=»auto»> и строит по нему новое число R следующим образом.

1) Число N переводим в двоичную запись.

2) К этой записи справа дописывается один разряд по следующему правилу: если количество единиц в двоичной записи числа больше количества нулей, то справа дописывается 1, иначе дописывается 0.

3) К полученной записи повторно применяется алгоритм из п.2.

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

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

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

for i in range(1, 1000):
    s = bin(i)[2:]
    if s.count(’1’) > s.count(’0’):
        s += ’1’
    else:
        s += ’0’
    if s.count(’1’) > s.count(’0’):
        s += ’1’
    else:
        s += ’0’
    if int(s, 2) < 99:
        print(int(s, 2))

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

Заметим, что алгоритм добавляет ту цифру, которых больше у числа (если количество равно, то добавляется нуль). Если у числа $N$ было какое-то количество нулей и какое-то количество единиц, то добавляя какую-то цифру, их количество только увеличивается, а значит и на следующем шаге добавят эту же цифру. Значит к числу добавят $11$ или $00$ .

Нам нужно найти наибольшее число $R$ , которое могли получить после работы данного алгоритма. Могло ли получиться число $9810 = 11000102$ ? Нет, так как оно кончается на 10, а мы знаем, что такое число не могло получиться после этого алгоритма.

Могло ли получиться число $97 = 1100001 10 2$ ? Нет, так как оно кончается на 01, а мы знаем, что такое число не могло получиться после этого алгоритма.

Могло ли получиться число $9610 = 11000002$ ? Такое число могло получиться после этого алгоритма, но давайте проверим какое число тогда было бы без добавленных нулей – если уберём два нуля, то получим число $110002$ , количество нулей больше, чем количество единиц, а значит к такому числу после работы алгоритма действительно добавляются два нуля, а значит 96 это наибольшее $R$ , которое могли получить после работы алгоритма.

Ответ: 96