Question

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

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

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

Accepted Answer

101

Answer

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

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

**Коды длины 1:** `0` и `1`
- `0` — префикс кодов `00` и `01` (К и Л), нарушает условие Фано.
- `1` — префикс кодов `100` и `110` (М и Н), нарушает условие Фано.

**Коды длины 2:** `00`, `01`, `10`, `11`
- `00` и `01` — уже заняты (К и Л).
- `10` — префикс кода `100` (М), нарушает условие Фано.
- `11` — префикс кода `110` (Н), нарушает условие Фано.

**Коды длины 3:** `100`, `101`, `110`, `111`
- `100` — совпадает с кодом М, нарушает условие Фано.
- `101` — не совпадает ни с одним существующим кодом и не является их префиксом; существующие коды не являются его префиксом. Условие Фано выполнено.
- `110` — совпадает с кодом Н, нарушает условие Фано.
- `111` — не совпадает ни с одним существующим кодом и не является их префиксом; существующие коды не являются его префиксом. Условие Фано выполнено.

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

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