Текущее задание ЕГЭ по информатике основано на кодирование информации и двоичного кода. Оно достаточно легко решается, если знать о бинарном дереве и условии Фано. Также же необходимо внимательно читать условие задачи (какой ответ необходимо указать).
Разберёмся со следующими терминами: бинарное дерево, неравномерный код, условие Фано и обратное условие Фано. Эти знания необходимы для успешного решения данной задачи. Обратное условие Фано очень редко попадается, но с ним лучше ознакомиться. Оно не сильно отличается от обычного условия Фано.
Бинарное дерево
Бинарное дерево — представляет собой дерево, растущее сверху вниз. Начинает свой рост с корня, далее идут “отростки” — ветви. В конце каждой ветви есть “узел”, на нём может располагаться какое-то значение, а могут образоваться новые ветви. Каждой ветви присуще двоичное представление, так сказать, её номер.
У номеров есть некоторые правила при построении дерева. Ветви, расположенные слева, номеруются нулями, а ветви справа — единицами. У узла могут быть только две ветви.
Как видно на рисунке, то в узлах второго уровня (в которых находятся буквы “А” и “Б”) есть значения, следовательно, от них ветви “пустить” уже не имеем права. Там, где зелёный узел можем создать ещё две ветви или присвоить какое-то значение, к примеру, букву “В”. У букв теперь есть двоичное представление, соответствующие условию Фано.
Неравномерный код
Неравномерный код очень легко определить. Посмотрим даже на таблицу выше, здесь для кодирования букв используется неравномерный код. Так как, для кодирования используется разное количество бит. Для букв “А” и “Б” — два бита, для буквы “В” — один.
Для равномерного кода букву “В” следует создать на втором уровня, тогда её код будет 01 или 00, и только для каждой буквы будет использоваться одинаковое количество бит.
Условие Фано
Условие Фано обычно описано в каждом задании, но всё же немного о нём поговорим. Оно звучит о том, что ни одно кодовое слово не может быть началом другого. Разберёмся на примере.
В данном случае наши кодовые слова не соответствуют условию Фано. У буквы “А” двоичное представление — единица. Она же является началом для букв “B” и “C”.
Обратное условие Фано
Обратное условие Фано очень похоже не обычное, но звучит немного иначе. Ни одно кодовое слово не может быть концом другого. Если в обычном условии мы проверяли сначала, то при обратном — с конца.
В текущем примере кодовые слова соответствуют условию Фано, но если рассматривать обратное условие, то нет. Здесь у буквы “А” двоичное представление тоже единица и оно же совпадает с концом у букв “B” и “C”.
Задание
Передаются сообщения, содержащие только четыре буквы: М, О, Р, Е; для передачи используется двоичный код, удовлетворяющий условию Фано. Для букв О, Р, Е используются такие кодовые слова: О: 111, Р: 0, Е: 100.
Укажите кратчайшее кодовое слово для буквы М. Если таких кодов несколько, укажите код с наибольшим числовым значением.
Решение
Получается, для большинства букв уже существуют кодовые слова, необходимо найти для буквы М.
Для решения задания воспользуемся бинарным деревом и расставим сразу известное.
На возможных местах поставим букву “М”. Отсюда видим, что у неё может быть два различных кодовых слова (101 и 100). Какой же выбрать? В задании сказано, что нужно найти кодовое слово с наибольшим численным значением — 101.
Понравилась статья? Хочешь разбираться в информатике, программировании и уметь работать в разных программах? Тогда ставь лайк, подпишись на канал и поделись статьей с друзьями! Остались или появились вопросы — спроси в комментариях!
Читайте также:
- Информатика ЕГЭ №1
- Информатика ЕГЭ №2 — решение с помощью языка программирования Python
- Информатика ЕГЭ №3 — решение в редакторе электронных таблиц OpenOffice Calc