ЕГЭ по информатике 2026, задание 4: кодирование и условие Фано

Задание 4 — базовое, 1 балл, без файла. Проверяют кодирование и декодирование. Главный инструмент — условие Фано: ни одно кодовое слово не является началом другого. Тогда строку из нулей и единиц можно декодировать однозначно слева направо.

Конспект

Условие Фано можно проверить деревом. Каждый код — путь от корня: 0 — левая ветка, 1 — правая. Кодовое слово должно заканчиваться в листе. Если чья-то буква стоит на пути к другой букве, код нефановский.

Типовые сюжеты:

• даны коды нескольких букв, нужно декодировать цепочку;
• даны коды части букв, нужно найти самое короткое, затем самое большое или маленькое кодовое слово для оставшейся буквы;
• выбрать набор кодов, который удовлетворяет Фано.

Перебор, который рекомендует ФИПИ: последовательно добавляйте бит и берите первое слово, которое ещё не является началом уже занятых кодов и само их не продолжает. Смотрите, что именно просят: минимальную длину, минимальное числовое значение среди самых коротких или слово целиком.

Нельзя «занять» остаток дерева так, что для ещё одной буквы места не останется. Если букв несколько и коды не заданы, сначала кодируйте те, для которых условие уже почти выбрало слово, и проверяйте, что остальным ещё есть листья.

Шаблон на Python

Проверка условия Фано и декодирование строки. Для поиска короткого свободного слова перебираются коды в порядке возрастания длины.

def is_fano(codes):
    for a in codes:
        for b in codes:
            if a != b and b.startswith(a):
                return False
    return True

def decode(bits, codes):
    inv = {v: k for k, v in codes.items()}
    i = 0
    out = []
    while i < len(bits):
        found = None
        for code, ch in inv.items():
            if bits.startswith(code, i):
                found = (code, ch)
                break
        if not found:
            return None
        out.append(found[1])
        i += len(found[0])
    return "".join(out)

codes = {"A": "00", "B": "01", "C": "1"}
print(is_fano(codes.values()), decode("00101", codes))

used = set(codes.values())

def free_words(max_len=6):
    words = [""]
    for _ in range(max_len):
        nxt = []
        for w in words:
            for bit in "01":
                cand = w + bit
                trial = list(used) + [cand]
                if is_fano(trial):
                    yield cand
                nxt.append(cand)
        words = nxt

print(next(free_words()))

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

• Кодовое слово совпало с началом уже занятого кода.
• Ищут минимальное число, но забывают, что сначала нужна минимальная длина.
• Декодируют справа налево. Фано читается слева направо.
• В ответ записывают слово вместе с лишними буквами, которые из цепочки не следуют.