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

Задание#T29749

По каналу связи передаются сообщения, содержащие только восемь букв: А, В, Е, З, И, Н, О, Р. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А – 101, В – 010, И – 0.

Какое наименьшее количество двоичных знаков потребуется для кодирования слова НЕВЕЗЕНИЕ?

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

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

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

Видно, что в дереве есть три свободных узла: 011 (длина кода 3), 100 (длина кода 3), 11 (длина кода 2). Нужно закодировать ещё пять букв (Е, З, Н,О, Р), три из которых входят в слово НЕВЕЗЕНИЕ. Чтобы количество знаков для кодирования этого слова было минимальным, нужно брать для букв Е, З, Н как можно более короткие коды, при этом самый короткий код надо использовать для буквы Е, которая встречается в заданном слове четыре раза; для буквы Н, которая встречается два раза, можно взять код более длинный, а для буквы З (один раз) – самый длинный.

Используем один из свободных узлов для расширения дерева. После этого получится четыре свободных узла. Три из них можно использовать для букв Е, З, Н, а четвёртый – для дальнейшего расширения дерева и кодирования букв О и Р, которые не входят в заданное слово.

Если расширить узел длины 2, то все коды букв Е, З, Н будут содержать по три бита, общая длина добавленных кодов для слова НЕВЕЗЕНИЕ составит

7 · 3 = 21.

Если расширить узел длины 3, то получится один свободный узел длины 2, один длины 3 и два длины 4. Если использовать код длины 2 для буквы Е, код длины 3 для Н и код длины 4 для З, то общая длина добавленных кодов составит

4 · 2 + 2 · 3 + 4 = 18.

Видно, что этот вариант выгоднее. Коды букв В и И заданы в условии, их общая длина – 5, итого получается 23 бита.

Ответ: 23

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

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

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

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

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

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

Задание#T29749

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

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

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