ГДЗ по информатике 10 класс Босова, номер §4 ПМ 4

§ ПМ Префиксный код

Усложним условие задачи. Теперь кодируемая последовательность состоит из букв А, Б, В, Г и Д. Кодовые слова для букв А, Б и В определены: А — 0, Б — 10, В — 110. Какими кодовыми словами могут быть закодированы буквы Г и Д? Код должен удовлетворять свойству однозначного декодирования. Общая длина кодовых слов для всех пяти букв должна быть минимальной.

Решение

Воспользуемся прямым условием Фано: ни одно кодовое слово не должно быть началом другого. Тогда сообщение можно читать слева направо без разделителей.

Всё поддерево, начинающееся с , уже занято кодом А. В поддереве ветвь занята кодом Б, а ветвь — кодом В. Свободной остаётся только ветвь .

Слово нельзя отдать одной из двух новых букв: тогда никакое другое слово, начинающееся с , использовать уже нельзя. Кроме того, здесь возникла бы неоднозначность: запись означала бы и букву с кодом вместе с А (код ), и отдельное слово , если отдать его другой букве.

Разветвим свободную ветвь ещё раз. Получатся два слова длины : и . Ни одно из пяти слов , , , , не служит началом другого. Длины слов составляют соответственно , , , и ; их сумма равна . Чтобы получить два разных слова в свободной ветви, оба должны иметь длину не менее , поэтому сумма минимальна.

Буквам Г и Д можно назначить эти два слова в любом порядке.

Ответ

Например, Г — , Д — ; минимальная общая длина кодовых слов — .

Помогло?

Номер §4 ПМ 4