Задание 4 ЕГЭ: условие Фано и дерево кодов

Что значит «однозначно декодировать»

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

Например, 0 и 01 вместе брать нельзя: первый код — начало второго. А 0 и 10 можно: ни один не начинается с другого. Это правило для кодов разной длины, а не требование, чтобы все коды имели одинаковую длину.

Авторская разминка: А кодируется как 0, Б — как 10, В — как 110. Выберите самый короткий код для Г так, чтобы выполнялось прямое условие Фано. Если несколько кодов одной длины подходят, выберите наименьший по числовому значению.

Как читать дерево

Из корня выходят две ветки: 0 и 1. Следующая ветка дописывает ещё один бит: из 1 получаются 10 и 11. Путь от корня — сам код, число пройденных веток — его длина.

Когда взяли 0, всё ниже него закрыто: 00, 01, 000 и так далее. Нельзя и подняться выше уже занятого кода: 1 запрещён, потому что является началом 10 и 110.

Почему ответ 111, а не 11

Однобитные варианты: 0 уже занят, 1 является началом существующих кодов. Двухбитные: 00 и 01 продолжают 0, 10 занят, 11 является началом 110. Значит, длины 1 и 2 невозможны.

На глубине 3 код 111 свободен. Он не продолжает ни один занятый код и не является началом другого. Ответ: 111; минимальная длина — 3 бита.

Проверка сообщения АБГ: 0 | 10 | 111 → 010111. Читая слева направо, сначала узнаём 0, затем 10, затем 111.

Проверка пары кодов через Python

codes = ['0', '10', '110', '111']
ok = True
for a in codes:
    for b in codes:
        if a != b and b.startswith(a):
            ok = False
print(ok)  # True

b.startswith(a) проверяет, начинается ли b с a. Здесь все коды различны; если в исходном списке есть одинаковые коды разных букв, это тоже ошибка, её нужно проверить отдельно. Замените 111 на 11: программа выведет False.

Код помогает проверить вариант. Самое короткое решение этой разминки — рассуждение по дереву, без перебора.

Что меняется в более сложных задачах

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

При обратном условии Фано сравнивают окончания кодов; для обычного дерева слева направо этот разбор напрямую не подходит. Всегда прочитайте точную формулировку.

Нарисуйте своё дерево в онлайн-черновике или перейдите к курсу ЕГЭ №4. Справка по str.startswith.

Проверьте себя

Сначала решите самостоятельно. Затем проверьте ответ или откройте объяснение.