Question

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

**Примечание.** Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает однозначную расшифровку закодированных сообщений.

Accepted Answer

16

Answer

Идея решения: построить префиксное дерево, где уже занятые коды (0 и 10) соответствуют листьям, и найти минимальные свободные коды для оставшихся четырёх букв.

Проанализируем структуру кодового дерева. Код `0` занимает левую ветвь корня (буква А). Код `10` занимает правую ветвь корня, затем левую подветвь (буква Б). Это означает, что правая подветвь от узла `1` остаётся свободной.

Свободные пути в дереве:
- Путь `11` (длина 2) — один узел.
- Пути `110`, `111` (длина 3) — два узла.
- Пути `1100`, `1101`, `1110`, `1111` (длина 4) — четыре узла.

Чтобы минимизировать сумму длин кодов для четырёх букв (В, Г, Д, Е), нужно использовать коды наименьшей длины. Однако если мы возьмём код `11` для одной буквы, то остальные три буквы не смогут использовать коды длины 2 или 3 (так как они начинаются с `11`). Это вынудит нас использовать коды длины 4 для трёх букв, что даст сумму $2 + 4 + 4 + 4 = 14$.

Если же мы используем коды `110`, `111` (длина 3) для двух букв, то для оставшихся двух букв остаются только коды длины 4, что даёт сумму $3 + 3 + 4 + 4 = 14$.

Оптимальный вариант — использовать все четыре кода длины 4: `1100`, `1101`, `1110`, `1111` для букв В, Г, Д, Е соответственно. Это даёт сумму $4 + 4 + 4 + 4 = 16$.

Проверим, что это действительно минимум. Любое распределение кодов длины 2 и 3 приводит к необходимости использовать коды длины 4 для оставшихся букв, что не улучшает результат. Таким образом, минимальная сумма равна 16.

Задание №4Представление информацииЕГЭ по информатике