Перейти к содержанию

Вот этот код: А − 01, Б − 11, В − 001, Г − 101, Д − 100

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность. Вот этот код: А − 01, Б − 11, В − 001, Г − 101, Д − 100.

Определите букву, для которой можно сократить длину кодового слова так, чтобы код по-прежнему можно было однозначно декодировать. Коды остальных букв меняться не должны. В ответе укажите букву и её сокращенное кодовое слово без пробелов и запятых. Например, А0.


Условие однозначного декодирования (условие Фано) заключается в том, что однозначное декодирование возможно, только если ни одно кодовое слово не является началом другого кодового слова. В данной задаче нужно просмотреть кодовые слова для каждой из букв и проверить будет ли выполняться условие Фано, если мы каким-нибудь образом сократим данное кодовое слово. Например, рассмотрим букву А – 01. Если заменить её код на 1, то он будет являться началом кодов букв Б, Г и Д. Если заменить код на 0, то он будет являться началом кода буквы В. Таким образом, при любом сокращении кода буквы А условие Фано нарушается. Проверив подобным образом все буквы, приходим к выводу, что можно сократить букву В, закодировав её словом 00. В таком случае нарушения условия Фано не произойдёт.

Ответ: в00

Другие задачи из этого раздела