Житель страны «МАШИНА» Егор шифрует слова. По каналу связи передаются сообщения, содержащие только заглавные латинские буквы. Для передачи используется двоичный код, удовлетворяющий прямому условию Фано. Кодовые слова для некоторых букв известны: M – 001, N – 010, P – 1000, Q – 1001, O – 111, R – 0110.
Укажите кратчайшее возможное кодовое слово для буквы W. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Примечание. Прямое условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Чтобы решить задачу, нам следует определить возможное положение кода, соответствующего букве ’W’, в дереве кодирования Фано.
В кодировании Фано, каждая буква представлена путём от корня дерева к одному из его листьев, где самый короткий путь соответствует кратчайшему коду.
Согласно принципу Фано, ни одно кодовое слово не может быть началом другого кодового слова. Это свойство сохраняется при представлении кодов в виде дерева, где каждый узел представляет собой бит (0 или 1), а каждый лист — букву. Следовательно, каждый путь от корня до листа представляет собой уникальный код для буквы.
После построения дерева можно заметить, что код 110 остается свободным. Так как он соответствует принципу Фано, то буква ’W’ может быть закодирована как 110. Ответ: 110.