Разбор задачи A9 (демо ЕГЭ 2012)
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г и Д, решили использовать неравномерный двоичный код, позволяющий однозначно декодировать двоичную последовательность, появляющуюся на приёмной стороне канала связи. Использовали код: А–1, Б–000, В–001, Г–011. Укажите, каким кодовым словом должна быть закодирована буква Д. Длина этого кодового слова должна быть наименьшей из всех возможных. Код должен удовлетворять свойству однозначного декодирования.
- 00
- 01
- 11
- 010
При однозначном декодировании в коде одного символа не должно быть дублирования(повторения) части кода другого символа. Т.к. длина кода должна быть наименьшей, то начнем с длины кода =1.
Возможные коды: 0, 1.
"0"-не подходит, т.к. он является частью кода букв: Б,В,Г
"1"-не подходит,т.к. таким кодом закодирована буква А
Возьмем длину кода =2.
Возможные коды: 00,01,10,11
"00"- не подходит, т.к. он является частью кода букв: Б,В
"01"- не подходит, т.к. он является частью кода буквы Г
"10" и "11"- не подходят, т.к. он начинается с "1", а этим кодом закодирована буква А
Возьмем длину кода =3.
Возможные коды: 000,001,010,011,100,101,110,111.
Сразу отбросим коды,которые начинаются с "1",т.к. этим кодом закодирована буква А.
"000"- не подходит, т.к. таким кодом закодирована буква Б
"001"- не подходит, т.к. таким кодом закодирована буква В
"010"- подходит, т.к. таким кодом ничего не закодировано