ЕГЭ-04. Кодирование и декодирование. Условие Фано.


Разберем решение аналогичной задачи на примере слова СЛОНОПОТАМ
Сначала определим число вхождений букв в слово
СЛОНОПОТАМ: {О}*3+{А,Л,М,Н,П,С,Т}*1
В слово входит восемь различных букв и еще одну позицию ("форточку")
надо оставить для того, чтобы была возможность закодировать остальные знаки.
Можно обозначить  "форточку" знаком * и кодировать из расчета 9 букв (знак * должен иметь самый длинный код)
Для 9 букв явно достаточно равномерного кода из 4 знаков, тогда длина кода для слова была бы 36 знаков.
Если использовать для самой частой буквы код из 3 знаков, то еще для 6 букв можно использовать код из 3 знаков, а для двух из 4 знаков (одна из них *).

В этом случае длина кода будет 9*3+4=31 знаку.
Если использовать для самой частой буквы код из 2 знаков, то еще для двух букв придется использовать коды из 4 знаков.

В этом случае длина кода будет 3*2+4*3+4*3=30
Если использовать для самой частой буквы код из 1 знака, то для оставшихся букв придется использовать код из 4 знаков.

В этом случае длина кода будет 3*1+7*4=31.
Пример оптимального кода (один из возможных вариантов) 
О А Л М Н П С Т *
00 010 011 100 101 1100 1101 1110 1111

 

Задача для тренировки:

ege-04_sem-FM-01

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация