Для передачи сообщений, содержащих только буквы К, Л, М, Н, О, П, Р, решили использовать неравномерный двоичный код, в котором никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Известны кодовые слова, использованные для некоторых букв: К – 11, Л – 000, П – 0010, Р – 1011. Какое кодовое слово надо назначить для буквы М, чтобы код удовлетворял указанному условию и при этом длина слова МОЛОКО после кодирования была наименьшей? Если таких кодов несколько, укажите код с наименьшим числовым значением.
Сначала рассмотрим уже известные кодовые слова: К – 11, Л – 000, П – 0010, Р – 1011. Обратим внимание, что никакое из этих кодовых слов не является началом другого кодового слова. Оно является началом, если нельзя дописать к кодовому слову какой-либо символ так, чтобы получилось другое кодовое слово.
Рассмотрим кодовое слово для буквы М. Это кодовое слово должно удовлетворять условию, то есть не должно быть началом другого кодового слова. В то же время, чтобы минимизировать длину слова "МОЛОКО" после кодирования, необходимо выбрать кодовое слово с наименьшим числовым значением.
Давайте рассмотрим числовые значения уже известных кодовых слов:
К – 11 (3 в десятичной системе числения)
Л – 000 (0 в десятичной системе числения)
П – 0010 (2 в десятичной системе числения)
Р – 1011 (11 в десятичной системе числения)
Мы видим, что минимальное числовое значение уже имеет кодовое слово для буквы Л (000), поэтому оно не может быть началом другого кодового слова М. Другими словами, в кодовом слове для буквы М должно быть добавлено хотя бы одно "1" перед кодом для Л.
Преобразуем код для Л, добавив в начало один символ "1". Получим код "1000".
Проверим, удовлетворяет ли этот код условию. Никакие другие кодовые слова не начинаются с 1, поэтому этот код является корректным и не является началом другого кодового слова.
Теперь рассмотрим длину слова "МОЛОКО", закодированного с использованием нового кода для М (1000).
М - 1000
О - код неизвестен
Л - 000
О - код неизвестен
К - 11
О - код неизвестен
Как видим, длина закодированного слова будет составлять 17 символов.
Однако, мы можем увидеть, что кодовое слово для Л (000) может быть сокращено до одного символа (0) без нарушения условия. Тогда новая длина закодированного слова будет составлять 15 символов.
Таким образом, кодовое слово для буквы М, удовлетворяющее условию и обеспечивающее наименьшую длину закодированного слова "МОЛОКО", будет 1000.