5.01 Запись числа в двоичной системе счисления

Решение программой
В условии задачи описан алгоритм, для поиска подходящего числа R необходимо «перевести» этот алгоритм с естественного языка на язык программирования Python. Сначала переводим число N в двоичную строку с помощью функции bin, затем вычисляем количество единиц и нулей с помощью метода count. Если единиц больше, дописываем 1, используя конкатенацию строк (оператор +). Иначе – дописываем 0. Повторяем те же действия для изменённой двоичной записи, переводим результат в десятичную систему счисления, получаем R.

Далее организуем перебор чисел N в цикле for. Для каждого полученного значения R проверяем, меньше ли оно 99 и является ли наибольшим среди полученных. Если условие выполняется, обновляем наибольшее значение R. После завершения цикла выводим максимальное R, которое смогли найти.

mx = -1000  # Инициализация переменной для хранения максимального R < 99
for i in range(1, 1000):  # Перебираем числа N от 1 до 999 включительно
    s = bin(i)[2:]  # Перевод в двоичную систему

    # Вычисляем количество единиц и нулей, сравниваем
    if s.count("1") > s.count("0"):
        # Если единиц больше, дописываем 1, иначе - 0
        s += "1"
    else:
        s += "0"

    # Повторяем предыдущий шаг, но уже для изменённой записи
    if s.count("1") > s.count("0"):
        s += "1"
    else:
        s += "0"

    r = int(s, 2)  # Переводим в десятичную систему

    # Проверяем, что r < 99, то есть подходит по условию, и больше текущего максимального
    if r < 99 and r > mx:
        mx = r
print(mx)

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

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

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

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

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