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


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

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв К, Л, М, Н, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы Н ис­поль­зо­ва­ли ко­до­вое слово 0, для буквы К — ко­до­вое слово 10. Ка­ко­ва наи­мень­шая воз­мож­ная сум­мар­ная длина всех четырёх ко­до­вых слов?

При­ме­ча­ние.

Усло­вие Фано озна­ча­ет, что ни­ка­кое ко­до­вое слово не яв­ля­ет­ся на­ча­лом дру­го­го ко­до­во­го слова. Это обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний.

Ре­ше­ние.

Найдём наи­бо­лее ко­рот­кие пред­став­ле­ния для всех букв. Ко­до­вые слова 01 и 00 ис­поль­зо­вать нель­зя, по­сколь­ку тогда на­ру­ша­ет­ся усло­вие Фано. Ис­поль­зу­ем, на­при­мер, для буквы Л ко­до­вое слово 11. Тогда для четвёртой буквы нель­зя по­до­брать ко­до­вое слово, не на­ру­шая усло­вие Фано. Сле­до­ва­тель­но, для остав­ших­ся двух букв нужно ис­поль­зо­вать трёхзнач­ные ко­до­вые слова. За­ко­ди­ру­ем буквы Л и М ко­до­вы­ми сло­ва­ми 110 и 111. Тогда сум­мар­ная длина всех четырёх ко­до­вых слов равна 1 + 2 + 3 + 3 = 9.

 

Ответ: 9.


Аналоги к заданию № 7658: 7685 Все