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




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

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

 

БукваКодовое слово
А0101
Б101
Г
Е011

 

БукваКодовое слово
И00
М0100
Р11
Т

 

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

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

Решение.

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

0 — нельзя, А, Е, И и М начинаются с 0.

1 — нельзя, Б и Р начинаются с 1.

00 — нельзя из-за И.

01 — нельзя из-за А, Е и М.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

 

Ответ: 1000.