Ах, ЕГЭ по информатике – это как поход в лес с картой, на которой нарисован только один треугольник и надпись «Тут где-то выход». В прошлый раз мы с вами успешно построили двоичные деревья и нашли кодовые слова для букв – почти как маленькие лесные эльфы, распределяющие коды по веточкам. Теперь же настало время перейти ко второму типу заданий, где нам придётся не просто сочинять кодовые слова, а ещё и считать, сколько же двоичных знаков понадобится для передачи целого слова.
В общем, математика встречается с лингвистикой на поле битвы двоичного кода!
Начнём с классики жанра – задания 400. Представьте себе: на связи у нас всего пять буквышек – Б, К, Л, О и Н. И вот уже нам дают пару готовых кодов: Б – 1001, К – 11. Остальные три буквы словно заблудились в лесу без карты, но мы им поможем!
Задача: закодировать слово «КОЛОКОЛ» так, чтобы длина кода была минимальной. Ну а если вы думаете, что это просто – вспомните анекдот про программиста: «Почему программисты путают Хэллоуин и Рождество? Потому что OCT 31 = DEC 25».
Вот так и здесь – нужно внимательнее считать.
Первое дело – подсчёт повторений букв в слове «колокол». Тут буква «О» главная звезда вечера: она встречается чаще всех остальных.
Значит ей полагается самый короткий код – иначе зачем вообще эти знания? Дальше строим двоичное дерево (воображаемое или реальное) и размещаем буквы на листьях так, чтобы условие Фано не нарушалось – то есть никакой код не должен быть префиксом другого. Это как если бы вы пытались объяснить бабушке по телефону рецепт пирога без лишних слов: каждый ингредиент должен звучать чётко и однозначно.
И вот левый лист свободен – значит туда идёт буква «О», которая теперь получает самый короткий код из доступных. Для оставшихся букв Л и Н выбираем два других листа: Л получает более короткий код «101», а Н довольствуется длинным «1000».
Конечно, можно было бы устроить конкурс красоты среди кодов или даже сделать голосование среди букв за лучший номер телефона!
Теперь считаем длину всех кодовых слов в слове «колокол»: складываем длины каждого кода с учётом количества повторений букв. Получается 13 двоичных знаков.
Выдохнули? Молодцы! Если бы это был шашлык из битов — можно было бы уже устраивать пикник.
Переключаемся на задание 406. Здесь у нас другой набор букв: Б, К, Р, О и Н.
Известны коды для Б (10), Н (110) и Р (000). Остались К и О без прописки в нашем цифровом городке. Нужно закодировать слово «КОРОБОК» минимально возможным количеством знаков.
Снова считаем повторения букв — тут О снова лидер по популярности! Построим симметричное двоичное дерево — представьте его как ёлку с украшениями-кодами на ветках.
Свободных листьев осталось три: 01, 001 и 111.
Самый короткий код отдан букве О (01), ну а К выбирает между двумя оставшимися вариантами — пусть будет 111 для разнообразия! Получаем полный набор кодов для всех букв.
Подсчитываем итоговую длину кода слова «коробок»: получается целых 17 двоичных знаков! Это примерно как посчитать калории после праздничного обеда — вроде немного цифр, но всё равно ощущение насыщения наступает быстро.
Честно говоря, работа с такими задачами напоминает мне историю про студента-программиста: он решил оптимизировать свой сон и поставил будильник так умно, что просыпался ровно через каждые две минуты всю ночь.
Итог? Он проснулся бодрым… но всего лишь минут на пять перед экзаменом!
Вот так иногда хочется сделать всё максимально эффективно — а потом понимаешь, что важна не только длина кода или сна, но ещё и качество!