Приветствую! Сегодня мы с Вами решим четвёртое задание из ЕГЭ по информатике.
Первое, с чего стоит начать - так это с условия Фано, название которого не фигурирует в задании, но описание точно подходит под него.
Никакое кодовое слово не является началом другого кодового слова.
Что это значит? Это означает, что не может быть ситуации, в которой одновременно сосуществуют два кодовых слова, к примеру, таких: 10, 100.
Так как закодированная последовательность 10011010110110... будет иметь неоднозначное раскодирование, т.к. непонятно, какой код стоит в начале: 10 или 100.
С этим разобрались, но как это обеспечить?
Можно следить вручную, глазками, но имея больше 6 кодовых слов, вероятность ошибки стремится к 100%. Нам такой вариант точно не подходит!
На помощь приходит двоичное дерево. Строится следующим образом: делаем ветвление, с одной стороны 0, с другой 1. Расположение не важно, желательно, чтобы оно было одинаковое. Например, я всегда ставлю 0 слева, а 1 - справа.
Ветвление может быть только из того места, где нет буквы.
Занесём закодированные кодовые слова из условия задачи.
Если двигаться с начала (обозначил красной точкой), то, собирая по пути циферки 0 и 1, можно собрать кодовое слово для любой буквы. Слева я выписал все буквы, подлежащие кодированию.
Важно: кодировать нужно абсолютно все перечисленные в задании буквы
Видим, что закодировать осталось 2 буквы, а свободное место одно: 10. Так дело не пойдёт, придётся делать ещё ветвление.
Теперь у нас есть 2 свободных места, как раз под оставшиеся П и Р.
Вопрос задачи в том, чтобы найти кратчайшее кодовое слово для П. Но 100 и 101 имеют равную длину 3. На такой случай в задании чётко сказано, что тогда нужно взять кодовое слово с наименьшим числовым значением.
Очевидно, что 100 < 101.
Ответ: 100
Минутка саморекламы :)
Если Вы не хотите пропустить выход разбора всех заданий демо-версии ЕГЭ по информатике, то советую подписаться на этот канал.
А если же Вам нужна профессиональная и быстрая подготовка к экзамену за адекватные деньги, то добро пожаловать на мой сайт. Кстати, сейчас там действует акция на групповые занятия до 4 человек (целых -40%), если у Вас есть друзья и знакомые, желающие подготовиться к ЕГЭ по информатике.