Question

Для кодирования последовательности из букв К, Л, М, Н, П, Р используется неравномерный двоичный код, удовлетворяющий условию Фано. Буквам К, Л, М, Н назначены коды 00, 01, 100, 110 соответственно. Найдите кратчайшее кодовое слово для буквы П, при котором сохраняется возможность однозначного декодирования. Если существует несколько кодов одинаковой минимальной длины, выберите код с наименьшим числовым значением.

Примечание. Условие Фано гарантирует, что ни один код не является началом другого кода, что обеспечивает однозначную расшифровку сообщений.

**Примечание.** Условие Фано гарантирует, что ни один код не является началом другого кода, что обеспечивает однозначную расшифровку сообщений.

Accepted Answer

101

Answer

Идея решения: проверить все возможные коды в порядке возрастания длины и числового значения, отсеивая те, которые нарушают условие Фано (являются префиксом или содержат существующий код как префикс).

Проанализируем, какие коды доступны:

**Длина 1:**
- `0` — недопустим, так как `00` и `01` начинаются с `0`.
- `1` — недопустим, так как `100` и `110` начинаются с `1`.

**Длина 2:**
- `00` — занят (буква К).
- `01` — занят (буква Л).
- `10` — недопустим, так как `100` начинается с `10`.
- `11` — недопустим, так как `110` начинается с `11`.

**Длина 3:**
- `100` — занят (буква М).
- `101` — свободен. Проверим: не является префиксом никакого существующего кода и не содержит ни один из них как префикс. ✓
- `110` — занят (буква Н).
- `111` — свободен, но длиннее `101`.

Кратчайший доступный код — `101` с числовым значением $101_2 = 5_{10}$.

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