Разбор задачи A9 (демо ЕГЭ 2013)
Для кодирования некоторой последовательности, состоящей из букв А, Б, В,
Г и Д, используется неравномерный двоичный код, позволяющий однозначно декодировать полученную двоичную последовательность.
Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
Вот этот код: А – 00, Б – 01, В – 100, Г – 101, Д – 110.
Можно ли сократить для одной из букв длину кодового слова так, чтобы код по-прежнему можно было декодировать однозначно? Коды остальных букв меняться не должны. Выберите правильный вариант ответа.
- для буквы Д – 11
- это невозможно
- для буквы Г – 10
- для буквы Д – 10
Решение:
Построим графы, образующие используемые коды:
На графе видно, что для букв А, Б, В и Г сократить длину кода нельзя.
Возьмем, к примеру, букву А. Ее код - 00. Сократим на 1 разряд и получим 0 (идем вверх от кода 00 по ветке графа). Тогда буква Б не сможет использоваться. Код буквы Б, 01, будет раскодирован как буква А, и останется нераскодированный код 1.
Поэтому сократить длину кода можно только для буквы Д. Идем вверх от кода 110 по ветке графа и получаем код 11.
Получили, буква Д с кодом 11.