№4 · решено
Четыре оставшиеся буквы
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны.
| Буква | Кодовое слово |
|---|---|
| Е | 10 |
| Ж | 010 |
| З | 011 |
| Д | 11 |
Какое наименьшее количество двоичных знаков требуется для кодирования четырёх оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: А, Б, В, Г. Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Источник: ФИПИ (демоверсия), № 23741
Ответвпиши то, что получилось
Показать разбор
- Нарисуй дерево: влево 0, вправо 1. Отметь известные коды из таблицы: Е 10, Д 11, Ж 010, З 011.
- Ветка 1 занята целиком, в ветке 0 занято всё, что начинается с 01. Свободен один узел 00.
- Букв осталось четыре, поэтому узел 00 надо делить, пока не получится четыре места.
- Для наименьшей суммы дели поровну, на одинаковую глубину.
- Сложи длины четырёх слов для А, Б, В и Г. Известные буквы не считай.