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


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

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

 

БукваКодовое слово
А00
Б010
В111
Г1100
Д1011

БукваКодовое слово
Е011
И1010
К1001
Л
М1000

 

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

 

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

Решение.

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

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

1 — нельзя, В, Г, Д, И, К и М начинаются с 1.

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

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

10 — нельзя из-за Д, И, К и М.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Таким образом, кодовым словом для буквы Л, удовлетворяющим условию Фано, является 1101.

 

Ответ: 1101.

Источник: ЕГЭ по информатике 13.06.2019. Основная волна, Восток. Вариант Имаева-Зубовой — «Котолис».