ИнформатикаЕГЭ

Впишите правильный ответ. — Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 00; для буквы

Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для буквы А использовали кодовое слово 00; для буквы Б – кодовое слово 01. Какова наименьшая возможная сумма длин кодовых слов для букв В, Г, Д, Е? Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.

Источник: ФИПИ — открытый банк заданий

Когда сказал «я сам решу» — и реально решил 😎
Разбор без магии

Ответы и решения

РРедакция «Я сам решу»Проверено

Коды 00 и 01 полностью занимают ветвь, начинающуюся с 0. Поэтому четыре оставшиеся буквы должны иметь коды, начинающиеся с 1. Минимальный вариант — использовать все четыре трёхбитовых слова 100, 101, 110 и 111. Они удовлетворяют условию Фано, а сумма их длин равна 3 + 3 + 3 + 3 = 12. Сделать сумму меньше невозможно: после общего первого бита нужно различить четыре буквы, для чего необходимы ещё два бита. Ответ: 12.