Question

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

| Буква | Кодовое слово |
|---|---|
| А | 00 |
| Б | 010 |
| В | 111 |
| Г | 1100 |
| Д | 1011 |
| Е | 011 |
| И | 1010 |
| К | 1001 |
| Л | ? |
| М | 1000 |

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

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

Accepted Answer

1101

Answer

Идея решения: перебрать все возможные двоичные коды в порядке возрастания длины и числового значения, проверяя для каждого, не является ли он префиксом или началом какого-либо из уже известных кодов.

Проверим коды длины 1:
- `0` — начало кодов А, Б, Е (не подходит).
- `1` — начало кодов В, Г, Д, И, К, М (не подходит).

Проверим коды длины 2:
- `00` — это сам код А (не подходит).
- `01` — начало кодов Б и Е (не подходит).
- `10` — начало кодов Д, И, К, М (не подходит).
- `11` — начало кодов В и Г (не подходит).

Проверим коды длины 3:
- `000`, `001`, `010`, `011` — начала или совпадения с кодами А, Б, Е (не подходят).
- `100`, `101`, `110`, `111` — начала или совпадения с кодами М, К, Д, И, Г, В (не подходят).

Проверим коды длины 4:
- `0000`, `0001`, `0010`, `0011` — начала кода А (не подходят).
- `0100`, `0101` — начала кода Б (не подходят).
- `0110`, `0111` — начала кода Е (не подходят).
- `1000` — это сам код М (не подходит).
- `1001` — это сам код К (не подходит).
- `1010` — это сам код И (не подходит).
- `1011` — это сам код Д (не подходит).
- `1100` — это сам код Г (не подходит).
- `1101` — не совпадает ни с одним известным кодом и не является началом ни одного из них (подходит!).

Код `1101` удовлетворяет условию Фано и является кратчайшим доступным кодом для буквы Л.

Задание №4Представление информацииЕГЭ по информатике