Базовый (1 балл) Время: 3-5 мин Python bin() int(s, 2) count() Все задачи №5 в каталоге

Задание №5. Автомат: из числа N делаем число R

Тема: Двоичная запись, подсчёт единиц и нулей, прямой и обратный поиск

Автомат берёт число N и по шагам строит из него число R, обычно работая с двоичной записью. Спрашивают либо минимальное N при заданном результате, либо результат при условии. Два способа: перебор и обратная логика.

Что от тебя хотят

Есть «автомат» с инструкцией: берём N, переводим в двоичную запись, что-то с ней делаем (дописываем, считаем, переворачиваем) и получаем число R. Тебя просят найти либо R для конкретного N, либо наименьшее N, при котором R получится нужным.

Четыре команды, которых хватит

Что нужно	Команда
Двоичная запись числа N	`bin(n)[2:]` (срез убирает приставку `0b`)
Количество единиц	`b.count("1")`
Из двоичной записи обратно в число	`int(b, 2)`
Дописать цифру справа	`b = b + "0"`

Способ 1: перебор «вперёд»

Если автомат простой, а ответ небольшой, пробуй N подряд: 1, 2, 3... Для каждого строй R по инструкции и проверяй условие. Первое подошедшее N и есть наименьшее.

К двоичной записи числа N справа дублируется последняя цифра. Затем справа дописывается бит чётности (остаток от деления количества единиц на 2), и та же операция выполняется для получившейся записи ещё раз. Результат — двоичная запись числа R. Найдите наименьшее N, при котором R больше 97.

Код из первого окна выдаёт 13: двоичная запись 1101, после дублирования 11011, после двух битов чётности 1101100, это 108. А у 12 получается 1100000, ровно 96, не хватило совсем чуть-чуть.

Способ 2: думаем «назад»

Если R огромное, а ответ получается в миллиардах, перебор N подряд застрянет. Тогда идём от результата обратно.

По двоичной записи числа N подсчитали количество единиц и количество нулей. Эти два числа записали в двоичной системе один за другим: сначала единицы, потом нули. Получили двоичную запись числа R. Найдите наименьшее N, при котором R = 314.

Двоичная запись 314 это 100111010. Это два числа, склеенные подряд: сначала число единиц, потом число нулей.
Не знаем, где граница. Пробуем все места разреза, но справа часть не может начинаться с нуля: в двоичной записи числа ведущих нулей нет.
Для каждого разреза получаем количество единиц и нулей. Например, 10011 и 1010 означают 19 единиц и 10 нулей.
Самое маленькое число с такими количествами: сначала единица, потом все нули, потом остальные единицы. Для 19 и 10 это 1 + 0000000000 + 18 единиц.
Среди всех разрезов выбираем наименьшее число. Результат второго окна: 268697599.

Заметил, что N выходит огромное? Перебор не подойдёт. Если в условии R велико, ответ часто лежит в миллионах и миллиардах. Тогда обратная логика единственный выход.

Разновидности и прототипы задания на экзамене

Тип 1: Дописываем бит справа

К двоичной записи N справа приписывают бит чётности или остаток, потом переводят обратно в число.

Тип 2: Считаем единицы и нули

Количества единиц и нулей записывают в двоичной системе одно за другим. Здесь перебор N не работает.

Тип 3: Другая система счисления

То же самое, только в троичной или пятеричной записи.

Код решения на Python

Запустить код в онлайн-песочнице

bin(n)[2:]b.count("1")int(b, 2)r[:cut]"0" * zerosmin(best, n)

Перебираем N по порядку

for n in range(1, 1000):
    b = bin(n)[2:]
    b = b + b[-1]
    b = b + str(b.count("1") % 2)
    b = b + str(b.count("1") % 2)
    r = int(b, 2)
    if r > 97:
        print(n)
        break

Задача из базы, которую решает этот код Открыть в песочнице

Идём от R обратно к N

r = bin(314)[2:]

best = 10 ** 20
for cut in range(1, len(r)):
    left = r[:cut]
    right = r[cut:]
    if right[0] == "0":
        continue
    ones = int(left, 2)
    zeros = int(right, 2)
    n = int("1" + "0" * zeros + "1" * (ones - 1), 2)
    best = min(best, n)

print(best)

Задача из базы, которую решает этот код Открыть в песочнице

Типичные ошибки

✕ Не так

Забыть срез у bin

bin(5) даёт '0b101': приставка попадёт в подсчёты и в склейку.

✓ Так

Всегда писать bin(n)[2:].

✕ Не так

Перебирать N до миллиарда

Для больших R цикл будет работать минуты, и ничего не найдёт.

✓ Так

Заметить, что N должно быть огромным, и разрезать двоичную запись R на две части.

✕ Не так

Разрезать R так, что справа часть начинается с нуля

В двоичной записи числа ведущих нулей нет.

✓ Так

Пропускать разрезы, где right[0] == "0".

ГРОБ

ГРОБ №5: Автомат в троичной записи

Инструкция работает не с двоичной, а с троичной записью. У Python нет готовой функции для перевода числа в троичную систему.

Как обойти

Переводи делением в цикле: s = "", пока n > 0 пиши s = str(n % 3) + s и делай n = n // 3. Обратно: int(s, 3).

Лайфхаки на экзамене

Количество единиц в двоичной записи считается командой b.count("1"). Нули считаются так же: b.count("0").
Наименьшее число с заданными количествами единиц и нулей: сначала 1, затем все нули, затем все остальные единицы.
Условие «наименьшее N»: идём по N в порядке возрастания и останавливаемся на первом подходящем. Условие «наибольшее»: идём вниз или берём максимум.

Банк реальных задач №5 Открыть в тренажере СмартКИМ