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




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

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

 

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

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

 

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

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

Решение.

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

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

1 — нельзя, буквы Б, Р и Т начинаются с 1.

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

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

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

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

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

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

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

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

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

 

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

 

Ответ: 101.