Задание 5: анализ алгоритмов и автоматов

Задание 5 (базовый уровень): автомат преобразует число по правилам — нужно найти исходное или итоговое значение.

Автомат в задании 5 — это фиксированный набор правил, которые по входному числу строят выходное (часто через его двоичную или десятичную запись и дописывание разрядов).

Что проверяет задание

Дан словесный алгоритм автомата: он берёт число, что-то делает с его записью (считает сумму цифр, дописывает разряды по правилу о чётности и т.п.) и выдаёт новое число. Вопрос обычно один из двух: «найдите результат для данного N» или «найдите наименьшее/наибольшее N, при котором результат удовлетворяет условию». Второй тип — это перебор, и здесь Python незаменим.

Разбор типового автомата

Рассмотрим автомат: на вход подаётся натуральное число N; строится его двоичная запись; если количество единиц в ней чётно — справа дописывается 0, иначе дописывается 11; получившаяся двоичная запись переводится в десятичное число — это результат R.

Сначала запрограммируем сам автомат и проверим его на нескольких числах:

def avtomat(n):
    s = bin(n)[2:]                  # двоичная запись без префикса 0b
    if s.count("1") % 2 == 0:       # чётное число единиц
        s = s + "0"
    else:                           # нечётное
        s = s + "11"
    return int(s, 2)                # обратно в десятичную

for n in [5, 6, 7]:
    print(f"N={n}  двоичное={bin(n)[2:]}  ->  R={avtomat(n)}")

Вывод:

N=5  двоичное=101  ->  R=10
N=6  двоичное=110  ->  R=12
N=7  двоичное=111  ->  R=31

Разберём N=7: двоичное 111, единиц три — нечётно, дописываем 11, получаем 11111 = 31. Логика автомата теперь в коде, и ошибиться в ручном переводе невозможно.

Тип «найди наименьшее N с условием»

Классическая формулировка: «Найдите наименьшее N, при котором результат работы автомата R больше 100». Перебираем N по возрастанию и берём первый подходящий:

def avtomat(n):
    s = bin(n)[2:]
    s = s + "0" if s.count("1") % 2 == 0 else s + "11"
    return int(s, 2)

answer = None
for N in range(1, 1000):
    if avtomat(N) > 100:
        answer = N
        break
print("наименьшее N:", answer, " даёт R =", avtomat(answer))

Вывод:

наименьшее N: 25  даёт R = 103

Проверим логику: 25 в двоичной записи — 11001, единиц три (нечётно), значит дописываем 11, получаем 1100111 = 103 > 100. Все числа меньше 25 дают результат не больше 100.

Метод обратного хода (когда дан результат)

Иногда дают результат R и просят восстановить исходное N, причём явного автомата для обращения нет. Тут два пути: либо аналитически «откатить» правила, либо — что надёжнее на КЕГЭ — перебрать все возможные N и оставить те, что дают нужный R:

def avtomat(n):
    s = bin(n)[2:]
    s = s + "0" if s.count("1") % 2 == 0 else s + "11"
    return int(s, 2)

target = 12
candidates = [N for N in range(1, 200) if avtomat(N) == target]
print("какие N дают R =", target, ":", candidates)

Вывод:

какие N дают R = 12 : [6]

Десятичные автоматы и сумма цифр

Бывают автоматы без двоичной записи — например, «припиши к числу справа сумму его цифр». Метод тот же: запрограммировать правило и перебрать.

# автомат: к числу справа дописывается сумма его цифр
def avtomat(n):
    digit_sum = sum(int(c) for c in str(n))
    return int(str(n) + str(digit_sum))

print("avtomat(45) =", avtomat(45))   # 4+5=9 -> 459
print("avtomat(28) =", avtomat(28))   # 2+8=10 -> 2810
# наименьший результат двух применений автомата
results = sorted((avtomat(avtomat(N)), N) for N in range(10, 100))
print("наименьший результат двух шагов:", results[0])

Вывод:

avtomat(45) = 459
avtomat(28) = 2810
наименьший результат двух шагов: (1012, 10)

Автомат с двумя приписываемыми разрядами

Очень частый на КЕГЭ автомат строит из числа N результат так: «Находится сумма S цифр двоичной записи N. Если S чётно — справа дописываются разряды 10, иначе 11; затем слева дописывается 1». Формулировки варьируются, но метод один: запрограммировать правило точно по тексту и перебрать. Найдём наибольшее N < 64, дающее результат меньше 200:

def avtomat(n):
    s = bin(n)[2:]
    suffix = "10" if s.count("1") % 2 == 0 else "11"
    return int("1" + s + suffix, 2)      # 1 слева, два разряда справа

best = None
for N in range(1, 64):
    if avtomat(N) < 200:
        best = N                          # запоминаем наибольшее подходящее
print("наибольшее N < 64 с результатом < 200:", best)
print("его результат:", avtomat(best))

Вывод:

наибольшее N < 64 с результатом < 200: 17
его результат: 198

Здесь перебор по возрастанию запоминает последнее подходящее N (то есть наибольшее), потому что цикл не прерывается, а перезаписывает best. Если бы мы искали наименьшее — поставили бы break на первом подходящем.

Типичные ловушки

• Префикс двоичной записи. bin(n) даёт '0b...' — обязательно отрезайте [2:], иначе подсчёт единиц будет неверным.
• «Наименьшее» или «наибольшее». Для наименьшего перебирайте по возрастанию и берите первый; для наибольшего — либо перебирайте до разумной границы и берите максимум, либо идите по убыванию.
• Несколько ответов. При обратном ходе подходящих N может быть несколько — выбирайте требуемый по условию.
• Порядок дописывания. Внимательно: дописывают слева или справа, к двоичной или к десятичной записи.

Итог

• Задание 5 — анализ автомата: запрограммируйте его правило один раз и используйте многократно.
• «Найди наименьшее/наибольшее N» — перебор по диапазону с проверкой условия.
• «Восстанови N по R» — перебор всех N и отбор тех, что дают нужный результат.