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

По ка­на­лу связи пе­ре­да­ют­ся со­об­ще­ния, со­дер­жа­щие толь­ко шесть букв: А, B, C, D, E, F. Для пе­ре­да­чи ис­поль­зу­ет­ся не­рав­но­мер­ный дво­ич­ный код, удо­вле­тво­ря­ю­щий усло­вию Фано. Для букв A, B, C ис­поль­зу­ют­ся такие ко­до­вые слова: А  — 11, B  — 101, C  — 0. Ука­жи­те ко­до­вое слово наи­мень­шей воз­мож­ной длины, ко­то­рое можно ис­поль­зо­вать для буквы F. Если таких слов не­сколь­ко, ука­жи­те то из них, ко­то­рое со­от­вет­ству­ет наи­мень­ше­му воз­мож­но­му дво­ич­но­му числу.

 

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

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

Ре­ше­ние.

По­сколь­ку все од­но­знач­ные и дву­знач­ные слова не под­хо­дят по усло­вию Фано, зна­чит, нужно найти трех­знач­ное слово, ко­то­рое было бы ми­ни­маль­но и удо­вле­тво­ря­ло усло­вию. Это слово  — 100. Од­на­ко при вы­бо­ре кода 100 мы за­кры­ва­ем воз­мож­ные ва­ри­ан­ты для D и E. Зна­чит, трех­знач­ные слова нам тоже не под­хо­дят. Если взять че­ты­рех­знач­ные, то там мы для ко­ди­ро­ва­ния можем взять слово 1000 (по­сколь­ку надо вы­брать ко­до­вое слово, со­от­вет­ству­ю­щее наи­мень­ше­му воз­мож­но­му дво­ич­но­му числу). Тогда для ко­ди­ро­ва­ния D и E можно ис­поль­зо­вать слова 10010 и 10011.

 

Ответ: 1000.


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

Источник: Тре­ни­ро­воч­ная ра­бо­та по ИН­ФОР­МА­ТИ­КЕ 11 класс 30 сен­тяб­ря 2016 года Ва­ри­ант ИН10103
Раздел кодификатора ФИПИ: