Задание 4 ЕГЭ по информатике: неравномерный код и условие Фано

Задание 4 ЕГЭ по информатике — про неравномерный двоичный код, в котором ни одно кодовое слово не совпадает с началом другого (условие Фано). Коды части букв известны, остальные нужно подобрать так, чтобы сообщение получилось самым коротким; удобнее всего это делать по двоичному дереву.

Как решать

Условие Фано требует, чтобы ни одно кодовое слово не совпадало с началом другого. Тогда сообщение декодируется однозначно: читая двоичную строку слева направо, вы всегда знаете, где заканчивается очередное кодовое слово.

Шаг 1. Нарисуйте двоичное дерево: из каждой вершины выходят две ветки, 0 и 1. Отметьте вершины известных кодовых слов. Под отмеченной вершиной другие коды ставить нельзя, на пути к ней тоже.

Шаг 2. Выпишите свободные вершины — самые верхние вершины, которые не лежат на пути к известным кодам и не находятся под ними. Длина кода, который можно поставить в свободную вершину, равна её глубине.

Шаг 3. Распределите свободные вершины между буквами без кода. Самые короткие коды отдайте буквам, которые чаще встречаются в слове. Если свободных вершин меньше, чем букв, одну вершину делят на две, и оба кода становятся на 1 длиннее.

Шаг 4. Посчитайте длину сообщения: для каждой буквы слова сложите длину её кода.

Для проверки на Python достаточно перебрать кодовые слова длиной до 5–6 знаков для неизвестных букв и проверить условие Фано для каждой пары. Программы из примеров работают быстрее секунды.

Примеры с решением

Пример 1

По каналу связи передаются сообщения, составленные из букв Ф, И, Л, О, С. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано. Известны кодовые слова трёх букв: О — 01, С — 100, И — 1110. Кодовые слова для букв Ф и Л неизвестны.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова ФИЛОСОФ?

Проверка ответа на Python

from itertools import product

known = {"О": "01", "С": "100", "И": "1110"}
unknown = ["Ф", "Л"]
word = "ФИЛОСОФ"

# Кандидаты в кодовые слова: все двоичные строки длиной от 1 до 6
candidates = ["".join(p) for n in range(1, 7) for p in product("01", repeat=n)]
best = None


def search(i, codes):
    """Подбираем коды неизвестным буквам по очереди, соблюдая условие Фано."""
    global best
    if i == len(unknown):
        length = sum(len(codes[ch]) for ch in word)
        best = length if best is None else min(best, length)
        return
    for w in candidates:
        if all(not w.startswith(c) and not c.startswith(w) for c in codes.values()):
            codes[unknown[i]] = w
            search(i + 1, codes)
            del codes[unknown[i]]


search(0, dict(known))
print(best)

Ответ: 18

По известным кодам 01, 100 и 1110 свободными остаются вершины 00, 101, 110 и 1111.

Буква Ф встречается в слове дважды, поэтому ей выгодно дать самый короткий свободный код 00. Букве Л достаётся код длины 3, например 101.

Длина слова ФИЛОСОФ: Ф 2 · 2 + И 4 + Л 3 + О 2 · 2 + С 3 = 4 + 4 + 3 + 4 + 3 = 18 знаков.

Пример 2

Для кодирования букв К, Р, Т, Н, У, М используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Р и Т выбраны кодовые слова 00, 011 и 101.

Какова наименьшая возможная сумма длин кодовых слов всех шести букв?

Проверка ответа на Python

from itertools import product

known = {"К": "00", "Р": "011", "Т": "101"}
unknown = ["Н", "У", "М"]

# Кандидаты в кодовые слова: двоичные строки длиной от 1 до 5
candidates = ["".join(p) for n in range(1, 6) for p in product("01", repeat=n)]
best = None


def search(i, codes):
    """Подбираем коды неизвестным буквам по очереди, соблюдая условие Фано."""
    global best
    if i == len(unknown):
        total = sum(len(c) for c in codes.values())
        best = total if best is None else min(best, total)
        return
    for w in candidates:
        if all(not w.startswith(c) and not c.startswith(w) for c in codes.values()):
            codes[unknown[i]] = w
            search(i + 1, codes)
            del codes[unknown[i]]


search(0, dict(known))
print(best)

Ответ: 16

Свободные вершины дерева: 11 (длина 2), 010 и 100 (длина 3). Букв без кода три, свободных вершин тоже три, поэтому каждая буква получает свою вершину. Если разделить свободную вершину на две, коды только удлинятся.

Сумма длин: 2 + 3 + 3 для К, Р, Т и 2 + 3 + 3 для Н, У, М, всего 16.

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

Потренироваться на тренажёре

Частые вопросы

Что такое условие Фано?

Это требование к неравномерному коду: ни одно кодовое слово не совпадает с началом другого. Такой код декодируется однозначно без разделителей между словами.

Можно ли решить задание 4 без дерева?

Можно перебирать кодовые слова по возрастанию длины и проверять, не начинается ли одно с другого. С деревом быстрее: свободные вершины видны сразу.

Сколько времени отводится на задание 4 ЕГЭ по информатике?

Около 2 минут — это самое короткое по времени задание в спецификации 2027 года. Верный ответ приносит 1 первичный балл.

Официальные материалы

Другие задания

Все задания и структура экзамена — на странице ЕГЭ по информатике. Соседние разборы: задание 3 и задание 5.

Описание задания сверено 28 сентября 2026 года со спецификацией 2027 года (документы 2027 года). Примеры составлены нами по структуре демоверсии, каждое решение запущено, и напечатанный им ответ совпадает с ответом на странице. Кодолимп не связан с разработчиками экзамена. Заметили неточность — напишите нам.