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