Задания
Версия для печати и копирования в MS Word
Тип 4 № 16032
i

Для ко­ди­ро­ва­ния не­ко­то­рой по­сле­до­ва­тель­но­сти, со­сто­я­щей из букв А, Б, В, Г, Д, Е, ре­ши­ли ис­поль­зо­вать не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для буквы А ис­поль­зо­ва­ли ко­до­вое слово 0; для буквы Б  — ко­до­вое слово 10. Ка­ко­ва наи­мень­шая воз­мож­ная сумма длин ко­до­вых слов для букв В, Г, Д, Е?

 

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

Спрятать решение

Ре­ше­ние.

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

Ко­до­вые слова не могут на­чи­нать­ся с 0, по­сколь­ку 0 яв­ля­ет­ся ко­до­вым сло­вом для буквы А. Ко­до­вым сло­вом для буквы В будет яв­лять­ся 1100, ко­до­вые слова 11, 110 и 111 ис­поль­зо­вать нель­зя, по­сколь­ку не по­лу­чит­ся за­ко­ди­ро­вать осталь­ные буквы таким об­ра­зом, чтобы воз­мож­ная сумма длин ко­до­вых слов для букв В, Г, Д и Е была наи­мень­шей. Ко­до­вым сло­вом для буквы Г будет яв­лять­ся 1101, для буквы Д  — 1110, а для буквы Е  — 1111.

Таким об­ра­зом, сумма крат­чай­ших ко­до­вых слов для букв В, Г, Д и Е будет рав­нять­ся 4 + 4 + 4 + 4  =  16.

 

Ответ: 16.

Источник: Де­мон­стра­ци­он­ная вер­сия ЕГЭ—2019 по ин­фор­ма­ти­ке
Раздел кодификатора ФИПИ: