Задача № 87
По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, В, Г, Д, Е, Ж и 3. Для передачи используется двоичный код, удовлетворяющий условию Фано.
Кодовые слова для некоторых букв известны:
| А | 000 |
| Б | 001 |
| В | 0101 |
| Г | 0100 |
| Д | 011 |
| Е | 101 |
Какое наименьшее количество двоичных знаков потребуется для кодирования двух оставшихся букв? В ответе запишите суммарную длину кодовых слов для букв: Ж, 3
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Демонстрационный вариант 2024 года
Прокрути, чтобы прочитать решение задачи
Ты уверен, что хочешь это сделать?
Удачного чтения!
Решение
В задании нужно закодировать восемь букв. Коды шести букв известны. Нам нужно найти всего два кода.
Кликайте по стрелкам, чтобы прочитать решение по шагам.
Чтобы определить свободные коды,
построим двоичное дерево.
Среди известных кодов есть те, которые начинаются с нуля и с единицы.
Поэтому развиваем каждую ветку.
Пока строим дерево, смотрим только на известные коды.
Кода, который бы начинался с двух единиц, среди известных нет.
Это первый свободный код — запомним его.
Остальные коды являются началом кодов известных букв.
Подпишем буквы.
Ветки дерева, на которых оказались буквы, развивать нельзя.
Посмотрим на другие коды.
Код «100» — свободный. Нет буквы, код которой начинался бы со ста.
Запомним его.
С кода «010» начинаются буквы «В» и «Г».
Добавим их на наше дерево.
Теперь посмотрим на все буквы, которые нужно закодировать.
Их восемь. Закодировано — шесть. Два кода свободны.
Получается, что буквам «Ж» и «З» можно отдать свободные коды.
В ответ нужно записать суммарную длину кодов букв «Ж» и «З».
Неважно, какой код достанется какой букве: суммарная длина будет равна пяти.