Question

Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Кодовые слова для пяти цветов:
- Белый — `0`
- Чёрный — `10`
- Красный — `1110`
- Фиолетовый — `11110`
- Зелёный — `11111`

Найдите кратчайшее кодовое слово для синего цвета, при котором код допускает однозначное декодирование (удовлетворяет условию Фано: ни один код не является началом другого).

Accepted Answer

110

Answer

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

Проанализируем занятые коды:
- `0` — занято (Белый)
- `10` — занято (Чёрный)
- `1110` — занято (Красный)
- `11110` — занято (Фиолетовый)
- `11111` — занято (Зелёный)

Проверим возможные коды для синего по возрастанию длины:

**Длина 1:** Единственный вариант `1` — но это префикс кодов `10`, `1110`, `11110`, `11111`. Не подходит.

**Длина 2:** 
- `00` — начинается с `0`, который уже является полным кодом. Не подходит.
- `01` — начинается с `0`, который уже является полным кодом. Не подходит.
- `11` — это префикс кодов `1110`, `11110`, `11111`. Не подходит.

**Длина 3:**
- `100` — начинается с `10`, который уже является полным кодом. Не подходит.
- `101` — начинается с `10`, который уже является полным кодом. Не подходит.
- `110` — не является префиксом и не содержит полные коды как префиксы (начинается с `11`, но `11` не полный код). Подходит!

Проверим условие Фано для `110`: ни один из существующих кодов не начинается с `110`, и `110` не является началом ни одного из них. Условие выполнено.

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