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

Решение 1

В этой задаче мы рассматриваем алгоритм, который строит новое число на основе двоичной записи исходного числа N и выполняет последовательное добавление битов в конец строки по определённым правилам. Сначала мы организуем перебор всех чисел N от 1023 вниз до 2 с помощью цикла for i in range(1023, 1, -1). Для каждого числа создаём его двоичную запись с помощью bin(i)[2:]. Здесь функция bin(i) возвращает строку вида ’0b...’, поэтому срез [2:] убирает префикс ’0b’, оставляя только последовательность нулей и единиц, которую сохраняем в переменной s.

Далее мы трижды повторяем шаг добавления нового бита: проверяем количество нулей и единиц в текущей строке s с помощью s.count(’0’) и s.count(’1’). Если количество нулей и единиц одинаково, добавляем в конец строки её последнюю цифру s[-1]. Если количество нулей меньше количества единиц, в конец добавляем ’0’, а если единиц меньше, добавляем ’1’. Для компактности решения используется комбинация логических выражений с умножением строк: s[-1] * (s.count(’0’) == s.count(’1’)) добавляет последнюю цифру при равенстве чисел нулей и единиц, а ’1’ * (s.count(’1’) < s.count(’0’)) + ’0’ * (s.count(’0’) < s.count(’1’)) добавляет реже встречающийся бит. Этот блок повторяется три раза, что реализует требование "Шаг 2 повторяется еще два раза".

После трёх итераций получаем финальную двоичную запись, которую преобразуем в десятичное число с помощью int(s, 2). Проверяем два условия: число должно быть нечётным (% 2 != 0) и делиться на 7 (% 7 == 0). Как только находится первое число, удовлетворяющее обоим условиям (так как мы перебираем числа в порядке убывания, оно будет наибольшим), выводим его с помощью print(i) и прерываем цикл командой break.

# Перебор чисел N от 1023 вниз до 2 включительно
for i in range(1023, 1, -1):
    # Получаем двоичную запись числа без префикса ’0b’
    s = bin(i)[2:]  # str: последовательность нулей и единиц

    # Трижды добавляем бит в конец строки по правилу задачи
    # Если количество нулей и единиц одинаково, добавляем последнюю цифру
    # Иначе добавляем бит, который встречается реже
    s += s[-1] * (s.count(’0’) == s.count(’1’)) + \
         ’1’ * (s.count(’1’) < s.count(’0’)) + \
         ’0’ * (s.count(’0’) < s.count(’1’))

    s += s[-1] * (s.count(’0’) == s.count(’1’)) + \
         ’1’ * (s.count(’1’) < s.count(’0’)) + \
         ’0’ * (s.count(’0’) < s.count(’1’))

    s += s[-1] * (s.count(’0’) == s.count(’1’)) + \
         ’1’ * (s.count(’1’) < s.count(’0’)) + \
         ’0’ * (s.count(’0’) < s.count(’1’))

    # Преобразуем итоговую двоичную запись в десятичное число
    # и проверяем, что число нечётное и делится на 7
    if int(s, 2) % 2 != 0 and int(s, 2) % 7 == 0:
        # Если условия выполнены, выводим наибольшее исходное число
        print(i)
        break

Решение 2

Сначала мы организуем перебор всех чисел N от 1023 до 2 включительно с помощью цикла for i in range(1023, 1, -1). Мы начинаем с 1023, чтобы сразу находить наибольшее подходящее число, и двигаемся вниз. Для каждого числа создаём его двоичную запись с помощью функции bin(i)[2:]. Здесь bin(i) возвращает строку вида ’0b...’, а срез [2:] убирает префикс ’0b’, оставляя только последовательность нулей и единиц. Эта строка сохраняется в переменной s.

Далее мы три раза повторяем шаг модификации строки, как требует условие задачи: считаем количество единиц и нулей в текущей записи с помощью s.count(’1’) и s.count(’0’), а затем находим разницу k = s.count(’1’) - s.count(’0’). Если разница отрицательна (k < 0), это значит, что нулей больше, и в конец строки добавляем ’1’, то есть бит, который встречается реже. Если разница положительна (k > 0), единиц больше, и в конец добавляем ’0’. Если разница равна нулю (k == 0), количество единиц и нулей одинаково, и в конец добавляем последнюю цифру текущей строки s[-1]. Мы выполняем эту операцию три раза, чтобы учесть три шага добавления бита.

После трёх итераций получаем финальную двоичную строку, которую преобразуем в десятичное число с помощью int(s, 2). Проверяем два условия одновременно: число должно быть нечётным (% 2 != 0) и делиться на 7 (% 7 == 0). Поскольку мы перебираем числа сверху вниз, как только находим число, удовлетворяющее обоим условиям, оно будет наибольшим, и мы выводим его с помощью print(i), после чего прерываем цикл командой break.

# Перебор чисел N от 1023 вниз до 2 включительно
for i in range(1023, 1, -1):
    # Получаем двоичную запись числа без префикса ’0b’
    s = bin(i)[2:]  # str: последовательность нулей и единиц

    # Повторяем три раза добавление нового бита по правилу задачи
    for j in range(3):
        # Вычисляем разницу между количеством единиц и нулей
        k = s.count(’1’) - s.count(’0’)

        # Если единиц меньше нулей, добавляем ’1’ в конец
        if k < 0:
            s += ’1’
        # Если единиц больше нулей, добавляем ’0’ в конец
        elif k > 0:
            s += ’0’
        # Если единиц и нулей поровну, добавляем последнюю цифру строки
        else:
            s += s[-1]

    # Преобразуем итоговую двоичную запись в десятичное число
    # и проверяем, что число нечётное и делится на 7
    if int(s, 2) % 2 != 0 and int(s, 2) % 7 == 0:
        # Если условия выполнены, выводим наибольшее исходное число
        print(i)
        break