Для кодирования некоторой последовательности, состоящей из букв
Формулировка задания: Для кодирования некоторой последовательности, состоящей из букв, используется неравномерный двоичный префиксный код. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
Задание входит в ЕГЭ по информатике для 11 класса под номером 5 (Кодирование и декодирование информации).
Рассмотрим, как решаются подобные задания на примере.
Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.
- кодовое слово для буквы Е можно сократить до 01
- кодовое слово для буквы К можно сократить до 1
- кодовое слово для буквы Н можно сократить до 10
- это невозможно
Рассмотрим все варианты ответа и выберем верный:
Вариант 1
Если мы сократим кодовое слово для буквы Е до 01, то код этой буквы можно будет перепутать с кодом буквы И (011). Это противоречит условию префиксного кода.
Вариант 2
Если мы сократим кодовое слово для буквы К до 1, то код этой буквы можно будет перепутать с кодом буквы Н (100). Это противоречит условию префиксного кода.
Вариант 3
Если мы сократим кодовое слово для буквы Н до 10, то не найдется ни одной буквы, начинающейся на 10. Следовательно, вариант подойдет в качестве ответа.
Вариант 4
Данный вариант неверен, так как в качестве ответа подошел вариант 3.
Таким образом, единственным верным ответом является ответ номер 3.
3
Нашли ошибку? Выделите текст и нажмите Ctrl + Enter.
Есть другой способ решения?