Продолжаем разбирать демоверсию ЕГЭ по информатике 2022 года. Рассматриваем задание №4, проверяющее умение кодировать информацию. Четвёртое задание не претерпело изменений: декодирование, условие Фано и бинарные деревья остались прежними.
Условие задачи
Для кодирования последовательности букв Л, М, Н, П, Р используется неравномерный двоичный код, удовлетворяющий условию Фано: никакое кодовое слово не является началом другого.
Для букв Л, М, Н используются кодовые слова 00, 01 и 11 соответственно:
- Л: 00
- М: 01
- Н: 11
Необходимо найти кратчайшее кодовое слово для буквы П, удовлетворяющее условию Фано. Если таких кодов несколько, выбирается код с наименьшим числовым значением. Также необходимо определить кодовое слово для буквы Р.
Решение задачи
Для решения задачи удобно использовать бинарные деревья. Дерево может начинаться с 0 или 1, и из каждой вершины могут выходить ветви с 0 и 1. Это помогает визуально определить возможные кодовые слова, соблюдая условие Фано.
Для букв Л (00) и М (01) использованы ветви из 0. Для буквы Н (11) — ветвь из 1.
Остаётся найти кодовые слова для П и Р, используя оставшиеся ветви. Так как ветвь, начинающаяся с 0, занята, начинаем с 1. Ветка 10 свободна.
Добавим к 10 продолжения: 100 и 101. Это даёт два возможных кода для П: 100 и 101. Выбираем 100, так как он имеет наименьшее числовое значение.
Ответ
Для буквы П кратчайшее кодовое слово с наименьшим числовым значением — 100. Код для буквы Р — 101.