Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 110
Условие
Для кодирования растрового рисунка, напечатанного с использованием шести красок, применили неравномерный двоичный код. Для кодирования цветов используются кодовые слова.
| Цвет | Кодовое слово |
|---|---|
| Белый | 0 |
| Зелёный | 11111 |
| Красный | 1110 |
| Цвет | Кодовое слово |
Синий |
| Фиолетовый | 11110 |
|---|---|
| Чёрный | 10 |
Укажите кратчайшее кодовое слово для кодирования синего цвета, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подсказки — как подойти к решению
- Выпиши все занятые кодовые слова и построй по ним двоичное дерево: цвет можно закодировать только словом, которое не является началом занятого слова и само не имеет занятых начал.
- Проверяй кандидатов по возрастанию длины: однобитные не подойдут (одно занято, а второе начинает другие коды), затем по очереди отбрасывай двубитные и трёхбитные, у которых есть занятое начало или занятое продолжение.
- Возьми самое короткое подходящее слово, а если подходящих одинаковой длины несколько — то, у которого меньше числовое значение в двоичной записи. В ответ впиши само кодовое слово.
Решение
Подберём кодовое слово для синего цвета. Слово 0 занято. Слово 1 является началом других кодов. Слово 10 занято. Слово 11 является началом других кодов. Слова 100 и 101 использовать нельзя, так как их начало совпадает с кодом черного цвета. Можно использовать только кодовое слово 110.
Ответ: 110.
Типичные ошибки
- Это слово является началом двух занятых кодов, поэтому однозначное декодирование нарушится. Проверяй не только начало слова, но и его продолжения.
- Слово начинается с уже занятого кода, значит расшифровка станет неоднозначной. Для каждого кандидата проверяй все его начала, а не только полное совпадение.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике