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

Задание#T4897

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

, Б – , И –

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

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

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

Указание:

Постройте дерево кодирования.

Решение:

Построим дерево кодирования.

Нужно закодировать ещё четыре буквы (В, Д, Е, Н), а в дереве есть три свободных узла. Каждое продолжение дерева из свободного узла создаёт два узла вместо одного, то есть количество узлов увеличивается на . Значит, нужно продолжить дерево в одном месте. С точки зрения длины кодов это можно сделать двумя способами:

из узла (длина кода ) получить два узла с длиной кода ;
из узла или (длина кода ) получить два узла с длиной кода .

В первом случае мы получим новые коды длиной , , , , во втором – , , , .

Подсчитаем количество знаков для кодирования слова ВВЕДЕНИЕ в каждом их этих случаев. В первом случае длина всех добавленных кодов (буквы В, Д, Е, Н) одинакова – бита. Длина кода буквы И задана – тоже бита. Всего получается

бита.

Во втором случае длина добавленных кодов разная. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы Е (она встречается чаще всех), следующим – код буквы В. Тогда длина кода для Е – бита, для В – , для Д и Н – по . Всего потребуется

бита.

Ответ: 23

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

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

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

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

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

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

Задание#T4897

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

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

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