№4 · решено
Код буквы B
По каналу связи передаются шифрованные сообщения, содержащие только десять букв: A, B, C, D, E, F, S, X, Y, Z; для передачи используется неравномерный двоичный код. Для кодирования букв используются кодовые слова.
| Буква | Кодовое слово | Буква | Кодовое слово |
|---|---|---|---|
| A | 00 | F | 1001 |
| B | S | 1100 | |
| C | 010 | X | 1010 |
| D | 011 | Y | 1101 |
| E | 1011 | Z | 111 |
Укажите кратчайшее кодовое слово для буквы B, при котором код удовлетворяет условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Источник: ФИПИ (открытый банк), № 29336
Ответвпиши то, что получилось
Показать разбор
- Выпиши девять известных кодов из таблицы, у буквы B кода нет.
- Нарисуй дерево: влево 0, вправо 1. Отмечай каждое слово как занятый лист, всё ниже него закрыто.
- Ветка 0 занята целиком: там 00, 010 и 011. Значит, код для B начинается с 1.
- Пройди ветку 1 по уровням сверху вниз и найди самый высокий свободный узел: не занятый и не лежащий на пути к занятому слову.
- Прочитай код этого узла по веткам. Если таких узлов несколько, бери самый левый, у него наименьшее значение.