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

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

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

for i in range(1, 1000):  # Перебираем числа N от 1 до 999 включительно
    s = bin(i)[2:]  # Перевод в двоичную систему

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

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

    if int(s, 2) > 78:  # Получаем R
        # Первое выведенное N будет минимальным
        print(i)  # Выводим N
        break  # Завершаем цикл

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

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

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

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

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

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