Question

Для кодирования последовательности из букв А, Б, В, Г, Д, Е используется неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г назначены кодовые слова: 100, 101, 00, 01 соответственно. Для букв Д и Е коды ещё не определены.

Найдите кратчайшее кодовое слово для буквы Д, при котором код допускает однозначное декодирование. Если существует несколько кодов одинаковой длины, выберите код с наименьшим числовым значением.

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

Accepted Answer

110

Answer

Идея решения: построить префиксное дерево для существующих кодов и найти кратчайший свободный путь, который не нарушает условие Фано.

Проанализируем занятые коды:
- А: 100
- Б: 101
- В: 00
- Г: 01

Проверим, какие коды длины 1 доступны:
- `0` — не подходит, так как является префиксом кодов `00` и `01`.
- `1` — не подходит, так как является префиксом кодов `100` и `101`.

Оба одноразрядных кода заняты или ведут в существующие коды.

Проверим коды длины 2:
- `00` — уже занят (буква В).
- `01` — уже занят (буква Г).
- `10` — является префиксом кодов `100` и `101`, не подходит.
- `11` — свободен и не является префиксом никакого существующего кода.

Однако `11` может быть началом более длинных кодов. Проверим коды длины 3:
- `110` — не является префиксом никакого существующего кода и не содержит существующих кодов как префикса.
- `111` — также свободен.

Кратчайшие доступные коды для буквы Д — это `110` и `111` (оба длины 3). Из них `110` имеет наименьшее числовое значение ($110_2 = 6_{10}$ против $111_2 = 7_{10}$).

Проверим, что `110` удовлетворяет условию Фано:
- Не является префиксом никакого из кодов А, Б, В, Г.
- Ни один из кодов А, Б, В, Г не является его префиксом.

Для буквы Е можно использовать `111`, и условие Фано остаётся выполненным.

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