СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости




Задания
Версия для печати и копирования в MS Word
Задание 5 № 10379

По каналу связи передаются сообщения, содержащие только буквы А, Б, В, Г, Д, Е. Для передачи используется неравномерный двоичный код, удовлетворяющий условию Фано; для букв A, Б, В используются такие кодовые слова: А — 0, Б — 101, В — 110.

Какова наименьшая возможная суммарная длина всех кодовых слов? Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова. Коды, удовлетворяющие условию Фано, допускают однозначное декодирование.

Решение.

Перечислим возможные коды в порядке возрастания длины. Стоит сразу сказать, что любой код, начинающийся с 0, не подходит, так как код А - 0, поэтому смотрим только на те, что начинаются с 1.

1 - нельзя, Б, В начинаются с 1.

10 - нельзя из-за Б.

11 - нельзя из-за В.

111 - можно использовать, пусть это будет код Д.

100 - также можно использовать, но если мы его возьмём, то не будет больше кодов, которые можно будет взять, так как все коды, начинающиеся с 0, уже нельзя брать, а все коды, начинающиеся с 1 и имеющие длину больше трёх, начинаются с одной из этих строк: 100, 101, 110, 111.

Рассмотрели все коды с длинами от 1 до 3, поэтому теперь достаточно взять любые два подходящие кода длины 4. Например, 1000 и 1001.

В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4 = 18.