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

Задание#T4816

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

, И – , С – .

Какое наименьшее количество двоичных знаков потребуется для кодирования слова КОЛОБОК?

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

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

Указание:

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

Решение:

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

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

Из узла (длина кода ) получить два узла с длиной кода , затем продолжить дерево из любого из трёх свободных узлов длины ;
Из узла (длина кода ) получить два узла с длиной кода , а затем из одного из них – два узла с длиной кода .

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

Подсчитаем количество знаков для кодирования слова КОЛОБОК в каждом из этих случаев. Очевидно, что для получения наименьшей длины самым коротким должен быть код буквы О (она встречается чаще всех), следующим – код буквы К.

В первом случае длина кода букв О и К – бит, букв Л и Б – бит, для кодирования слова КОЛОБОК потребуется

бит.

В любом случае для кодирования слова КОЛОБОК потребуется минимум двоичных знака.

Ответ: 23

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

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

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

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

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

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

Задание#T4816

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

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

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