Задание 5. Кодирование и расшифровка сообщений: Демоверсия егэ по информатике 2020: объяснение и решение
*** КАНАЛ ЮТЬЮБ ***
ЕГЭ по информатике -> ЕГЭ 2020 -> ЕГЭ 2020
Разбор 5 задания. Демоверсия егэ по информатике 2020, ФИПИ:
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Для кодирования некоторой последовательности, состоящей из букв К, Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию Фано. Для букв К, Л, М, Н использовали соответственно кодовые слова 000, 001, 010, 11. Для двух оставшихся букв – П и Р – длины кодовых слов неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять условию Фано. Если таких кодов несколько, укажите код с наименьшим числовым значением.
📹 Видеоразбор демоверсии егэ 2020
✍ Решение:
- Решим задание, используя построение дерева. Влево будем откладывать нули, вправо — единицы. Сначала отобразим на дереве известные кодовые слова:
- Чтобы соблюсти условие Фано, нельзя продолжать ветвь с уже установленной буквой. Т.е., например, ниже «листа» с буквой К ничего быть не должно. То же самое касается остальных букв.
- Доставим в оставшиеся возможные места буквы П и Р, обращая внимание на то, что для буквы П мы должны получить наименьшую длину кодового слова:
- Для буквы П получили кодовое слово 10.
Результат: 10