По каналу связи передаются сообщения, содержащие только десять букв: А, Б, В, Г, Д, Е, И, К, Л, М. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны:
|
|
Укажите кратчайшее кодовое слово для
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Перечислим возможные коды (не использующиеся для кодировки других букв) в порядке возрастания длины и числового значения.
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.