№4 · решено
Код буквы Л
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: А, Б, Е, И, К, Л, Р, С, Т, У; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.
| Буква | Кодовое слово | Буква | Кодовое слово |
|---|---|---|---|
| А | 01 | Л | |
| Б | 1001 | Р | 1000 |
| Е | 001 | С | 1010 |
| И | 000 | Т | 1101 |
| К | 1011 | У | 111 |
Укажите кратчайшее кодовое слово для буквы Л, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Источник: ФИПИ (досрочная волна), № 28752
Ответвпиши то, что получилось
Показать разбор
- Выпиши девять известных кодов из таблицы, у буквы Л кода нет.
- Нарисуй дерево: влево 0, вправо 1. Отмечай каждое слово как занятый лист, всё ниже него закрыто.
- Ветка 0 занята целиком: там 000, 001 и 01. Значит, код для Л начинается с 1.
- Пройди ветку 1 по уровням сверху вниз и найди самый высокий свободный узел: не занятый и не лежащий на пути к занятому слову.
- Прочитай код этого узла по веткам. Если таких узлов несколько, бери самый левый, у него наименьшее значение.