Базовый (1 балл)
Время: 2-4 мин
Python
bin()
int(s, 2)
Строковые срезы
Все задачи №{ topic_num } в каталоге
Задание №5. Анализ и построение алгоритмов для автоматов
Тема: Побитовые манипуляции, двоичная и n-ичная запись, остатки от деления и поиск N / R
Автомат преобразует натуральное число N в число R по заданному пошаговому алгоритму. На Python решается прямым перебором N в диапазоне от 1 до 1000 за 5 секунд.
1. Функции Python для Задания №5:
bin(n)[2:]— перевод числа $n$ в двоичную строку (срез[2:]отрезает служебный префикс'0b').b.count('1')— количество единиц в двоичной записи (в точности равно сумме цифр двоичного числа!).b.count('1') % 2— бит четности суммы цифр.int(b, 2)— перевод двоичной строки обратно в десятичное целое число $R$.int(s, 3)— перевод троичной строки в десятичное число.
2. Пошаговый алгоритм решения:
- Запускаем цикл перебора
for n in range(1, 1000):. - Формируем двоичную (или троичную) запись числа $N$.
- В точности применяем шаги алгоритма автомата через конкатенацию строк (
b = b + '01'). - Переводим полученную строку в десятичное число $R = \text{int}(b, 2)$.
- Проверяем условие задачи (например, $R > 123$) и сохраняем пару $(N, R)$ в список.
- Выводим минимальное или максимальное $N$ / $R$ по вопросу задачи.
Разновидности и прототипы задания на экзамене
Тип 1: Дописывание битов четности в двоичной записи
К двоичной записи N дописываются биты четности в конец (сумма цифр mod 2).
Тип 2: Позиционная обработка разрядов и срезы
Удаление первого/последнего символа двоичной строки с дописыванием остатков.
Тип 3: Алгоритмы в троичной и n-ичной системах счисления
Перевод N в 3-ичную СС делением с остатком и дописывание остатка от деления на 3.
Боевой шаблон решения на Python
Запустить код в онлайн-песочнице# === Боевой шаблон Задания №5 ЕГЭ на Python ===
# 1. Классический автомат с битами четности:
results = []
for n in range(1, 1000):
b = bin(n)[2:]
# Шаг 1: дописываем остаток от деления суммы цифр на 2:
b += str(b.count('1') % 2)
# Шаг 2: повторяем операцию:
b += str(b.count('1') % 2)
r = int(b, 2)
# Условие задачи (например, R > 97):
if r > 97:
results.append((n, r))
# Если просят минимальное R:
print("Минимальное R > 97:", min(r for n, r in results))
# Если просят минимальное N, для которого R > 97:
print("Минимальное N:", min(n for n, r in results))
# -------------------------------------------------------------
# 2. Автомат в троичной системе счисления:
def to_base3(n):
if n == 0: return '0'
res = ''
while n > 0:
res = str(n % 3) + res
n //= 3
return res
results3 = []
for n in range(1, 1000):
s = to_base3(n)
if n % 3 == 0:
s += s[-2:] # дописываем последние 2 цифры
else:
s += to_base3((n % 3) * 5)
r = int(s, 3)
if r > 133:
results3.append((n, r))
if results3:
print("Троичный автомат: мин. R:", min(r for n, r in results3))Анти-примеры (Типичные ошибки vs Как делать правильно)
Как делать НЕ надо:
Ошибка: Забыть срез [2:] у bin(n)
Строка '0b101' вместо '101' исказит подсчет длины и конкатенацию битов!Как делать ПРАВИЛЬНО:
Правильно: ВСЕГДА писать bin(n)[2:]Как делать НЕ надо:
Ошибка: Использовать bin(int(b, 2) + 1) на строках
Переводить строку в число и обратно туда-сюда вместо простой склейки строк.Как делать ПРАВИЛЬНО:
Правильно: Модифицировать двоичную запись напрямую как строку: b += '10'
ГРОБ
ГРОБ №5: Автомат в 3-ичной или 5-ичной системе счисления
Алгоритм работает в недвоичной системе счисления и требует дописывания остатков.
Как обойти ловушку: Напишите вспомогательную функцию `def to_base(n, base): s = ''; while n: s = str(n%base) + s; n //= base; return s or '0'` и переводите обратно через `int(s, base)`.
Лайфхаки и подводные камни на экзамене:
- Сумма цифр двоичного числа считается одной командой: `b.count('1')`.
- Диапазона `range(1, 1000)` хватает для 99.9% задач №5 ЕГЭ.
- Если требуется найти наименьшее R — используйте `min(r for n, r in results)`, если наименьшее N — `min(n for n, r in results)`.