СДАМ ГИА: РЕШУ ЕГЭ
Образовательный портал для подготовки к экзаменам
Информатика
≡ информатика
сайты - меню - вход - новости


Задания
Версия для печати и копирования в MS Word
Задание 5 № 10406

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко буквы А, Б, В, Г, Д, Е. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано; для букв A, Б, В ис­поль­зу­ют­ся такие ко­до­вые слова: А — 1, Б – 010, В – 001.

Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех ко­до­вых слов? При­ме­ча­ние. Усло­вие Фано озна­ча­ет, что ни одно ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Коды, удо­вле­тво­ря­ю­щие усло­вию Фано, до­пус­ка­ют од­но­знач­ное де­ко­ди­ро­ва­ние.

Ре­ше­ние.

Пе­ре­чис­лим воз­мож­ные коды в по­ряд­ке воз­рас­та­ния длины. Стоит сразу ска­зать, что любой код, на­чи­на­ю­щий­ся с 1, не под­хо­дит, так как код А - 1, по­это­му смот­рим толь­ко на те, что на­чи­на­ют­ся с 0.

0 - нель­зя, Б, В на­чи­на­ют­ся с 0.

01 - нель­зя из-за Б.

00 - нель­зя из-за В.

000 - можно ис­поль­зо­вать, пусть это будет код Д.

011 - также можно ис­поль­зо­вать, но если мы его возьмём, то не будет боль­ше кодов, ко­то­рые можно будет взять, так как все коды, на­чи­на­ю­щи­е­ся с 1, уже нель­зя брать, а все коды, на­чи­на­ю­щи­е­ся с 0 и име­ю­щие длину боль­ше трёх, на­чи­на­ют­ся с одной из этих строк: 011, 010, 001, 000.

Рас­смот­ре­ли все коды с дли­на­ми от 1 до 3, по­это­му те­перь до­ста­точ­но взять любые два под­хо­дя­щие кода длины 4. На­при­мер, 0111 и 0110.

В сумме длина кодов 1 + 3 + 3 + 3 + 4 + 4 = 18.