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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко буквы из на­бо­ра: А, Б, К, Р, Н. Для пе­ре­да­чи ис­поль­зу­ет­ся дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Это усло­вие обес­пе­чи­ва­ет воз­мож­ность од­но­знач­ной рас­шиф­ров­ки за­ко­ди­ро­ван­ных со­об­ще­ний. Ко­до­вые слова для не­ко­то­рых букв из­вест­ны: К  — 01, Р  — 001. Для трёх остав­ших­ся букв Б, Н и А ко­до­вые слова не­из­вест­ны. Какое ко­ли­че­ство дво­ич­ных зна­ков по­тре­бу­ет­ся для ко­ди­ро­ва­ния слова БА­РА­БАН, если из­вест­но, что оно за­ко­ди­ро­ва­но ми­ни­маль­но воз­мож­ным ко­ли­че­ством дво­ич­ных зна­ков?

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

Ре­ше­ние.

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

Ко­до­вым сло­вом не могут быть ни 0, ни 1, по­то­му что есть ко­до­вые слова, на­чи­на­ю­щи­е­ся с 0, а если за­ко­ди­ро­вать букву ко­до­вым сло­вом 1, то, за­ко­ди­ро­вав все буквы, по­лу­чим не крат­чай­шее ко­ли­че­ство дво­ич­ных зна­ков. Буквы А и Б за­ко­ди­ру­ем ко­до­вы­ми сло­ва­ми 10 и 11 со­от­вет­ствен­но, по­сколь­ку они по­вто­ря­ют­ся в слове БА­РА­БАН чаще всего. Букву Н за­ко­ди­ру­ем остав­шим­ся ко­до­вым сло­вом 000. Таким об­ра­зом, всего по­тре­бу­ет­ся 2 · 5 + 3 · 2  =  16 дво­ич­ных зна­ков.

 

Ответ: 16.

Источник: ЕГЭ по ин­фор­ма­ти­ке 04.04.2022. До­сроч­ная волна