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


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

По каналу связи передаются сообщения, содержащие только восемь букв: А, Б, Г, Е, И, М, Р, Т. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:

 

БукваКодовое слово
А11
Б0010
Г100
Е0011

 

БукваКодовое слово
И
М01
Р000
Т

 

Укажите кратчайшее кодовое слово для буквы И. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.

Ре­ше­ние.

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

0 — нель­зя, Б, Е, М и Р на­чи­на­ют­ся с 0.

1 — нель­зя, А и Г на­чи­на­ют­ся с 1.

00 — нель­зя из-за Б и Р.

01 — нель­зя из-за М.

10 — нель­зя из-за Г.

11 — нель­зя из-за А.

000 — нель­зя из-за Р.

001 — нель­зя из-за Е.

010 — нель­зя из-за М.

011 — нель­зя из-за М.

100 — нель­зя из-за Г.

101 — нель­зя, по­сколь­ку, если за­ко­ди­ро­вать букву И ко­до­вым сло­вом 101, для буквы Т не будет ко­до­вых слов, удо­вле­тво­ря­ю­щих усло­вию Фано.

110 — нель­зя из-за А.

111 — нель­зя из-за А.

0000 — нель­зя из-за Р.

0001 — нель­зя из-за Р.

0010 — нель­зя из-за Б.

0011 — нель­зя из-за Е.

0100 — нель­зя из-за М.

0101 — нель­зя из-за М.

0110 — нель­зя из-за М.

0111 — нель­зя из-за М.

1000 — нель­зя из-за Г.

1001 — нель­зя из-за Г.

1010 — можно ис­поль­зо­вать.

1011 — можно ис­поль­зо­вать.

1100 — нель­зя из-за А.

1101 — нель­зя из-за А.

1110 — нель­зя из-за А.

1111 — нель­зя из-за А.

 

Таким об­ра­зом, наи­мень­шее чис­ло­вое зна­че­ние у ко­до­во­го слова 1010 для буквы И.

 

Ответ: 1010.