Задание №4 ЕГЭ Информатика с ответом и решением
Ответ: 010
Условие
Для кодирования некоторой последовательности, состоящей из букв А, Б, В, Г, Д, Е, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв А, Б, В, Г использовали соответственно кодовые слова 000, 001, 10, 11. Укажите кратчайшее возможное кодовое слово для буквы Д, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Примечание. Условие Фано означает, что никакое кодовое слово не является началом другого кодового слова. Это обеспечивает возможность однозначной расшифровки закодированных сообщений.
Подсказки — как подойти к решению
- Нарисуй двоичное дерево и отметь занятые кодовые слова: свободными остаются только те ветви, которые не начинаются с готового слова и не содержат его внутри себя.
- Проверяй не только префиксность, но и размещаемость: слишком короткое слово может занять единственную свободную ветвь, и другой букве кода не останется. Из равных по длине вариантов бери меньший по значению.
Решение
Однозначные коды не подходят по условию Фано. Кратчайшее подходящее кодовое слово — 01. Но выбирая его, не останется вариантов закодировать букву E, значит, нужно взять минимум трехзначный код. Минимальный из них, подходящий по условию Фано — 010. Тогда букву Е можно закодировать как 011.
Ответ: 010.
Типичные ошибки
- Слово выбрано слишком коротким: оно занимает целую ветвь дерева, и для последней буквы места не остаётся — сначала убедись, что свободных слов хватает всем буквам.
В тренажёре: подсказки по шагам, разбор твоей ошибки ИИ-репетитором (он не даёт готовый ответ), повторение ошибок по интервалам и общий прогресс. Все задания №4 по информатике