Отправлено: 13.04.22 01:37. Заголовок: вариант 5 задание 4

Добрый день!

(166 № 3504) (Е. Джобс) По каналу связи передаются сообщения, содержащие только семь букв: О, К, Т, Я, Б, Р, Ь. Для передачи используется двоичный код, допускающий однозначное декодирование. Кодовые слова для некоторых букв известны: К – 1010, Т – 100, Б – 0101, Р – 110, Ь – 001. Укажите минимальную возможную сумму длин кодов всех букв.

Если строить дерево, то получается свободных три листочка: 000, 011 и 111, но в таком случае, ответом будет число 23. Правильно ли я понимаю, что при кодировании, в конкретном случае, "листочек можно и оборвать" т.е. букву Я, например, закодировать кодом 11, поскольку он (код) не является концом другого кода, если исключить код 111?

Спасибо!

 Отправлено: 13.04.22 13:35. Заголовок: Этот код удовлетворя..

Этот код удовлетворяет как прямому, так и обратному условию Фано, поэтому нужно проверить оба варианта. Простроив дерево для обратного условия Фано (по обратным кодам), можем выбрать открытые ветки 11 и 001. Сумма кодов 22.

 Отправлено: 13.04.22 15:31. Заголовок: Спасибо, Константин ..

Спасибо, Константин Юрьевич!