№№ заданий Пояснения Ответы Ключ Добавить инструкцию Критерии
Источник Раздел кодификатора ФИПИ Справка
PDF-версия PDF-версия (вертикальная) PDF-версия (крупный шрифт) PDF-версия (с большим полем) Версия для копирования в MS Word
Задания
Задание 5 № 11341

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

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

Ре­ше­ние.

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

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

 

 

Сум­мар­ная длина та­ко­го кода 1 + 2 + 4 + 4 + 4 + 4 = 19.

 

Ответ: 19.

· · Видеокурс ·