По каналу связи передаются сообщения, содержащие только четыре буквы: П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100.
Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Источник: демоверсия ФИПИ по информатике и ИКТ 2016-го года.
В решении задания есть видеоразбор
Решение:
Неравномерный код, допускающий однозначное декодирование, должен соответствовать условию Фано. По условию Фано в неравномерном префиксном коде ни одно кодовое слово не может быть началом другого слова. К примеру, если буква А имеет код 01, а буква Б — 0, то такое кодирование не соответствует условию, так как код буквы Б является началом кода буквы А.
Нам даны коды:
Т: 111
О: 0
П: 100
Код буквы С может начинаться только с единицы, так как если он будет начинаться с нуля, то код буквы О будет началом кода буквы С.
Коды 10 и 11 также не подходят, так как в этом случае код буквы С будет началом кодов букв Т и П.
100 не подходит, так как этот код уже является кодом буквы П, получается, что наименьший возможный вариант — 101.
