ГлавнаяИнформатикаКак решатьДля кодирования некоторой последовательности, состоящей из букв

Для кодирования некоторой последовательности, состоящей из букв

2016-05-24 14:08:38

Формулировка задания: Для кодирования некоторой последовательности, состоящей из букв, используется неравномерный двоичный префиксный код. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа. Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

Задание входит в ЕГЭ по информатике для 11 класса под номером 5 (Кодирование и декодирование информации).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

Для кодирования некоторой последовательности, состоящей из букв У, Ч, Е, Н, И и К, используется неравномерный двоичный префиксный код. Вот этот код: У — 000, Ч — 001, Е — 010, Н — 100, И — 011, К — 11. Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему остался префиксным? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.

Примечание. Префиксный код — это код, в котором ни одно кодовое слово не является началом другого; такие коды позволяют однозначно декодировать полученную двоичную последовательность.

  1. кодовое слово для буквы Е можно сократить до 01
  2. кодовое слово для буквы К можно сократить до 1
  3. кодовое слово для буквы Н можно сократить до 10
  4. это невозможно

Решение:

Рассмотрим все варианты ответа и выберем верный:

Вариант 1

Если мы сократим кодовое слово для буквы Е до 01, то код этой буквы можно будет перепутать с кодом буквы И (011). Это противоречит условию префиксного кода.

Вариант 2

Если мы сократим кодовое слово для буквы К до 1, то код этой буквы можно будет перепутать с кодом буквы Н (100). Это противоречит условию префиксного кода.

Вариант 3

Если мы сократим кодовое слово для буквы Н до 10, то не найдется ни одной буквы, начинающейся на 10. Следовательно, вариант подойдет в качестве ответа.

Вариант 4

Данный вариант неверен, так как в качестве ответа подошел вариант 3.

Таким образом, единственным верным ответом является ответ номер 3.

Ответ: 3

Есть другой способ решения?

Наверх