Все заглавные буквы русского алфавита закодированы неравномерным двоичным кодом, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова первых букв алфавита: А – 001, Б – 011, В – 110. Какую наименьшую длину может иметь код слова ВОДОПРОВОД?
Ответы
Ответ:
28
Объяснение:
Расставим приоритеты. В слове ВОДОПРОВОД
В - встречается 2 раза
О - встречается 4 раза
Д - встречается 2 раза
П - встречается 1 раз
Р - встречается 1 раз
Код для буквы В нам изначально задан, значит оставшиеся нам надо распределить. Для буквы О надо выдать наиболее короткий код, т.к она встречается чаще всех.
Строим дерево
А - 001, Б - 011, В - 110
Самый короткий из оставшихся кодов - 10. Его отдаём букве О
Т.к буква Д встречается 2 раза, а П и Р всего 1, под букву Д ставим код 111
Далее, остаются 000 и 010. Т.к в алфавите закодированы ВСЕ заглавные буквы русского алфавита, мы не можем просто так их отдать буквам П и Р. Тогда продолжим ветку 000, и получим: П - 0000, Р - 0001
Имеем:
В - 110
О - 10
Д - 111
П - 0000
Р - 0001
Считаем:
2 * 3 + 4 * 2 + 3 * 2 + 1 * 4 + 1 * 4 = 28
