По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е, Ж, З. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
А — 0
Б — 110
В — 111
Г — 1010
Д — 1011
Каждой из оставшихся букв (Е, Ж, З) присваивается возможное наименьшее по длине свободное слово.
Какое суммарное количество двоичных знаков займут кодовые слова букв Е, Ж и З?
В ответе запишите целое число.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
А — 0
Б — 110
В — 111
Г — 1010
Д — 1011
Каждой из оставшихся букв (Е, Ж, З) присваивается возможное наименьшее по длине свободное слово.
Какое суммарное количество двоичных знаков займут кодовые слова букв Е, Ж и З?
В ответе запишите целое число.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подсказка 1. Постройте дерево префиксов по известным словам и найдите свободные ветви.
Подсказка 2. Свободна ровно одна ветвь, поэтому слова придётся получать последовательным делением ветви.
Подсказка 3. Единственная свободная ветвь — 100 (длина 3); делим её: 1000 и 1001 (длины 4), затем одну из них ещё раз: получаем слова длиной 4, 5 и 5.
Разбор.
Приём — дерево префиксов и условие Фано. Известные слова занимают ветви 0, 110, 111, 1010, 1011, поэтому все три новые буквы размещаются в единственной свободной ветви 100. Делим её: 1000 достаётся первой букве (длина 4), вторую и третью размещаем глубже — делим ветвь 1001: 10010 и 10011 (длины 5 и 5). Итоговые длины: 4, 5 и 5, сумма 4 + 5 + 5 = 14.
Ответ: 14.
Ответ.
14