Question

Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы Н использовали кодовое слово 0, для буквы К — кодовое слово 110. Какова наименьшая возможная суммарная длина всех четырёх кодовых слов?
1)7
2)8
3)9
4) 10

Answer 1

Для анализа соблюдения условия однозначного декодирования (условия Фано) изобразим коды в виде дерева. Тогда однозначность выполняется, если каждая буква является листом дерева:
 
Легко заметить, что ближайшие от корня свободные листы (т.е. свободные коды с наименьшей длиной) — это 10 и 111. Таким образом, наименьшая возможная суммарная длина всех четырёх кодовых слов будет 1 + 3 + 2 + 3 = 9.
Правильный ответ указан под номером 3.
Ответ: 3.