Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Решать данное задание мы будем при помощи дерева кодирования: которое позволяет соблюсти условие Фано. Влево будем откладывать нули, вправо — единицы. Сначала отобразим на дереве известные кодовые слова:
Напомним, чтобы соблюсти условие Фано, нельзя начинать ветвь из листа (из буквы).
Проанализировав дерево, замечаем, что имеются два узла, из которых можно начать по одной ветке:
Таким образом, для недостающих букв у нас получилось два кодовых слова: 011 и 10 (стоит заметить, что буквам может соответствовать любое из этих кодовых слов).
В ответе необходимо указать код с наименьшим числовым значеним - 10.
Ответ: 10.
