Разборы · ЕГЭ, задание 4

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

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

Для передачи букв используется неравномерный двоичный код, удовлетворяющий условию Фано. Коды части букв известны; нужно подобрать коды остальных так, чтобы сообщение или код одной буквы был как можно короче. 1 балл.

Что нужно знать

• Условие Фано: ни одно кодовое слово не является началом другого. Тогда сообщение расшифровывается однозначно.
• Коды удобно рисовать двоичным деревом: от корня влево — 0, вправо — 1. Кодовое слово — лист дерева; ниже занятого листа ничего ставить нельзя, и сам лист нельзя ставить на пути к другому коду.
• Чем чаще буква встречается в сообщении, тем короче должен быть её код.

Как решать

1. Нарисуйте дерево и отметьте известные коды.
2. Выпишите свободные ветки: самые короткие двоичные слова, которые не являются началом известных кодов и не начинаются с них.
3. Раздайте свободные слова буквам: самой частой — самое короткое.
4. Посчитайте длину сообщения: сумма по буквам «число вхождений × длина кода».

Пример из демоверсии 2027

Буквы Б, К, Л, О, Н; известны коды Б — 00, Н — 010, Л — 111. Какое наименьшее количество двоичных знаков нужно для слова КОЛОБОК?

Решение. Слова длины 1 заняты: 0 — начало кода 00, 1 — начало кода 111. Из слов длины 2 свободно только 10 (01 — начало 010, 11 — начало 111). Из слов длины 3 свободны 011 и 110. В слове КОЛОБОК три буквы О и две К, поэтому О = 10, К = 011. Длина: 3 · 2 + 2 · 3 + 3 (Л) + 2 (Б) = 17.

Проверка перебором всех кодов длиной до 5 для К и О:

from itertools import product

known = {"Б": "00", "Н": "010", "Л": "111"}
words = ["".join(p) for n in range(1, 6) for p in product("01", repeat=n)]

def fano(codes):
    return len(set(codes)) == len(codes) and \
        all(a == b or not b.startswith(a) for a in codes for b in codes)

best = None
for k in words:
    for o in words:
        codes = dict(known, К=k, О=o)
        if fano(list(codes.values())):
            total = sum(len(codes[ch]) for ch in "КОЛОБОК")
            best = total if best is None else min(best, total)
print(best)                                  # 17

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

• Проверяют условие Фано только в одну сторону: новый код не должен быть началом старого и старый — началом нового.
• Дают короткий код редкой букве, а частой — длинный.
• Забывают про буквы, которые встречаются в слове один раз, — их коды тоже входят в сумму.

Потренироваться: задание 4 новые варианты с проверкой ответа