5 Разбор примера — по шагам
Разбор примера — по шагам
Возьмём типичную задачу первого типа и решим её через дерево.
Условие Для кодирования букв А, Б, В, Г, Д используют неравномерный двоичный код, удовлетворяющий условию Фано. Известно: А = 00, Б = 01, В = 11. Найдите наименьшую возможную сумму длин кодов всех пяти букв. |
Шаг 1. Отмечаем занятые коды на дереве
Рисуем дерево и ставим известные коды: 00 (А), 01 (Б), 11 (В). Каждый из них — занятый лист. Ветки под ними закрыты.
Шаг 2. Ищем свободные ветки
Смотрим, что осталось. Ветка 0 целиком занята буквами А и Б (00 и 01). Под единицей: 11 занята буквой В, а вот ветка `10` полностью свободна — это единственное свободное место.
Шаг 3. Сажаем оставшиеся буквы в самую короткую свободную ветку
Осталось разместить две буквы — Г и Д. Свободна ветка 10 (длина 2). Одну букву прямо в 10 посадить нельзя: тогда для второй уже не останется места по условию Фано. Значит, делим ветку 10 надвое: получаем 100 и 101. Сажаем: Г = 100, Д = 101.
Шаг 4. Считаем сумму длин
Буква | Код | Длина |
|---|---|---|
А | 00 | 2 |
Б | 01 | 2 |
В | 11 | 2 |
Г | 100 | 3 |
Д | 101 | 3 |
Сумма: 2 + 2 + 2 + 3 + 3 = 12.
Ответ: 12 |
💡 Почему именно так — и не короче Свободна была только ветка |