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

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

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

mn = 10 ** 10  # Инициализация переменной для хранения минимального R > 212

for i in range(1, 10000):  # Перебираем числа N от 1 до 9999 включительно
    s = bin(i)[2:]  # Перевод в двоичную систему
    s += ’1’  # Дописываем единицу

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

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

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

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

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

Каким бы не было число, на втором шаге к нему всегда дописывается единица, так что давайте называть это число «изначальным».

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

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

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

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

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

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

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

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

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

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

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

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

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