Неравномерный двоичный код: у частых букв слова короче.
Решаем деревом — в черновике, за две-три минуты.
Базовый уровень, один балл. Ответ — одно число или одно кодовое слово.
А – 0, Б – 01, В – 10. Пришло
сообщение 010. Что это?
0 | 10 — это АВ01 | 0 — это БА
Код не годится: получатель не поймёт, что прислали.
Беда в том, что 0 (А) — начало 01 (Б):
на дереве А сидит на пути к Б.
Никакое кодовое слово не является началом другого кодового слова.
Тогда расшифровка однозначна: читаем слева и отрезаем слово, как только оно совпало с кодом какой-то буквы, — другой буквы с таким началом нет.
На ЕГЭ это примечание печатают прямо в условии. Условие обратное Фано (ни одно слово не является концом другого) в 14 разобранных задачах 2025–2027 не встречалось.
Свободная ветвь — узел, куда не легло ни одно слово и через который не идёт путь к слову (пунктир). Новые буквы садятся только туда.
Б – 00, Н – 010, Л – 111 (демоверсия 2027)
Свободная ветка длины d — это:
Каждое деление удлиняет слова на один знак. Поэтому делить надо короткие ветки, а короткие слова — частым буквам.
свободная ветка 11 поделена на три буквы: 110, 1110, 1111
Разобраны 14 задач — демоверсии 2026 и 2027, волны, резервы, пересдачи, ЕГКР и апробации 2025–2026 годов.
| вопрос | задач | что считаем |
|---|---|---|
| длина закодированного слова | 9 | сумма «сколько раз × длина» по буквам слова |
| сумма длин слов оставшихся букв | 3 | то же, каждая буква по разу |
| кратчайшее кодовое слово для буквы | 2 | самый высокий свободный узел, левый |
Все три решаются одним деревом.
Буквы: Б, К, Л, О, Н. Известно: Б – 00, Н – 010, Л – 111. Для К и О слова неизвестны. Сколько двоичных знаков нужно для слова КОЛОБОК, если оно закодировано минимально возможным количеством знаков?
1. Дерево: свободные ветви 011,
10, 110.
2. Частоты в слове: О — 3 раза, К — 2. Буква Н в слове не встречается, но код у неё уже есть.
3. Ветвей хватает, делить не надо. Самое
короткое — частой: О → 10, К → 011.
4. К 2·3 + О 3·2 + Л 1·3 + Б 1·2 = 17
Н – 00, К – 01. Для Д, И, О, Р слова неизвестны. Свободна одна ветка —
1, а букв четыре: делим. Частоты: О — 2, Р — 2, Д — 1, И — 1.
поровну: О 2·3 + Р 2·3 + Д 3 + И 3 = 18
лесенкой: О 2·2 + Р 2·3 + Д 4 + И 4 = 18
Способов поделить ветку несколько — сравни два-три и возьми меньший. Здесь поровну. Плюс К 1·2: ответ 20.
Буквы А, Н, Р, С, Т, Я. Известно: С – 00, Р – 010, Н – 11. Для А, Т, Я
слова неизвестны. Свободны 10 и 011.
А → 10, Т → 011: 3·2 + 2·3 = 12, плюс С, Р, Н — 7. Ответ 19. Неверно: для Я места не осталось.
А → 10, ветку 011 делим: Т → 0110, Я → 0111. 3·2 + 2·4 = 14, плюс 7 — 21.
Восемь букв А–З. Известно: Е – 10, Ж – 010, З – 011, Д – 11. Какое наименьшее количество двоичных знаков нужно для четырёх оставшихся букв А, Б, В, Г?
Свободна одна ветка — 00. Четыре
буквы в одну ветку длины 2: делим дважды, 4 слова длины 4.
4 + 4 + 4 + 4 = 16
Здесь все буквы «по разу» — частоты нет, остаётся только делить экономно.
Десять букв, девять слов известны, у Л слова нет. «Укажите кратчайшее кодовое слово для буквы Л… Если таких кодов несколько, укажите код с наименьшим числовым значением».
Строим дерево по девяти словам. Свободной
оказывается ровно одна ветка — 1100.
Кратчайшее — самый высокий свободный узел. Если их несколько на одной глубине — левый: у него меньше значение.
Ответ: 1100