Question

Для кодирования последовательности используется таблица кодовых слов:

| Буква | Кодовое слово |
|---|---|
| А | 00 |
| Б | 1001 |
| В | 1010 |
| Г | 110 |
| Д | 0101 |
| Е | ? |
| Ж | 011 |
| З | 111 |
| И | 0100 |
| К | 1000 |

Найдите кодовое слово минимальной длины для буквы Е, удовлетворяющее условию Фано (ни один код не является началом другого). Если существует несколько кодов одинаковой минимальной длины, выберите код с наименьшим числовым значением.

Accepted Answer

1011

Answer

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

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

**Коды длины 2:**
- `00` — буква А (занято)
- `01` — ведёт к кодам длины 3 (Д: `0101`, И: `0100`)

**Коды длины 3:**
- `011` — буква Ж (занято)
- `010` — ведёт к кодам длины 4 (Д: `0101`, И: `0100`)

**Коды длины 3, начинающиеся с `1`:**
- `100` — ведёт к кодам длины 4 (К: `1000`)
- `101` — ведёт к кодам длины 4 (В: `1010`)
- `110` — буква Г (занято)
- `111` — буква З (занято)

**Коды длины 4:**
- `1001` — буква Б (занято)
- `1000` — буква К (занято)
- `1010` — буква В (занято)
- `1011` — свободно ✓

Проверим, что `1011` не нарушает условие Фано:
- Не является началом ни одного из существующих кодов
- Ни один из существующих кодов не является его началом

Коды длины 3 все заняты или ведут в коды большей длины, поэтому минимальная длина для Е равна 4. Среди 4-битных кодов свободен только `1011`.

![Рисунок](https://inf-ege.sdamgia.ru/get_file?id=147780)

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