Условие
Решение
Составим дерево, вершинами которого будут известные коды букв. Все коды начинаются на ноль. По условию Фано, коды, которыми закодированы буквы, дальше разбивать нельзя, так как получится, что у разных кодов будет одинаковое начало. По дереву видно, что все ветки тупиковые, а это значит, что оставшиеся буквы будем кодировать кодами начиная с единицы.
Остается закодировать три буквы: Е, Ж и З. Для этого нам нужно выделить три кода. Так как передаются только восемь букв, полученные коды также могут быть тупиковыми, то есть без возможного разбиения дальше.
Разобьем единицу на два кода: 10 и 11. Дальнейший выбор кода для разбивки не имеет значение, так как нам нужно закодировать оставшиеся символы суммарно минимальным количеством двоичных знаков.
Разобьем код 10, получим два кода 100 и 101. Код 11 разбивать не будем, сейчас ровно три свободных кода. Присвоим буквам коды — в любом порядке.
Буквы можно не подписывать, так как уже на данном этапе понятно, что тремя кодами можно закодировать три буквы
В итоге получим три кода: 100, 101 и 11. Их суммарная длина равна 8.
Ответ
8