По каналу связи передаются сообщения, содержащие только восемь букв: К, Л, М, Н, О, П, Р, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К... | Яндекс.Репетитор

Задание#T29776

По каналу связи передаются сообщения, содержащие только восемь букв: К, Л, М, Н, О, П, Р, С. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: К – 001, Н – 100, Р – 111. Какое наименьшее количество двоичных знаков потребуется для кодирования слова МОЛОКОСОС?

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Показать разбор и ответ

Построим дерево кодирования для заданных букв.

Видно, что в дереве есть четыре свободных узла: 000 (длина кода 3), 01 (длина кода 2), 101 (длина кода 3), 110 (длина кода 3). Нужно закодировать ещё пять букв (Л, М, О, П, С), четыре из которых входят в слово МОЛОКОСОС.

Один из свободных узлов нужно использовать для расширения дерева. Если расширить узел длины 2, то все буквы будут кодироваться тремя двоичными символами и длина кода для слова МОЛОКОСОС составит 9 ⋅ 3 = 27 бит.

Если расширить узел длины 3, то получится один узел длины 2, два узла длины 3 и два узла длины 4. Чтобы количество знаков для кодирования слова МОЛОКОСОС было минимальным, нужно брать для букв Л, М, О, С как можно более короткие коды, при этом самый короткий код надо использовать для буквы О, которая встречается в заданном слове четыре раза; для буквы С, которая встречается два раза, можно взять код более длинный, а для букв Л и М (по одному разу) – самый длинный. С учётом уже заданного кода для К получаем 4 ⋅ 2 + 2 ⋅ 3 + 3 + 4 + 3 = 24 бита.

Ответ: 24

Это задание составили эксперты «СтатГрада» для Яндекса

Это задание решали 8 тыс. раз. С ним справились 40% пользователей.

Это задание в разделах:

Формальное исполнение алгоритма, записанного на естественном языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченным набором команд

Это задание в тестах:

Тренировочный вариант ЕГЭ по информатике №44

Задание#T29776

Это задание в разделах:

Это задание в тестах:

Рекомендованные задания