Ах, ЕГЭ по информатике — тот самый экзамен, который заставляет даже самых стойких абитуриентов задуматься: а не стать ли мне лучше баристой?
Но сегодня мы не о кофе и не о бессонных ночах перед экзаменом. Сегодня мы окунёмся в загадочный мир кодов, двоичных деревьев и условия Фано — да-да, того самого условия, которое звучит как имя какого-то древнего фараона, но на самом деле всего лишь гарантирует, что наши коды не перепутаются. Представьте: вы шлёпаете по клавишам, а компьютер отвечает вам загадками — вот где настоящая магия!
В двух прошлых статьях мы уже научились отличать нули от единичек так виртуозно, что Цезарь бы позавидовал нашему шифру.
Мы разбирались в том, как устроена информация внутри компьютера — да-да, та самая непонятная штука с кучей проводов и светящихся лампочек. Условие Фано стало для нас как старый добрый друг: «Не волнуйся, я помогу тебе понять, какой код за какой буквой скрывается». Строили двоичные деревья — это такие штуки с ветвями и листьями, только без садовника и комаров.
Теперь настал момент истины — применить всё это знание на практике и решить четыре задания ЕГЭ по информатике.
Звучит страшно? Не переживайте!
Это как собирать пазл из кусочков… которые сами пытаются сбежать. Обычно в задании дают алфавит из нескольких букв и часть кодов уже известна (как будто кто-то подглядывал). Ваша задача — найти недостающий код для определённой буквы или сочетания букв так, чтобы всё соответствовало условию Фано и длина кода была минимальной. Иначе говоря: нужно вписать последний пазл так аккуратно, чтобы он идеально подошёл.
Если представить двоичное дерево как огромный автобус с местами для букв (каждое место — узел дерева), то нам нужно посадить пассажиров так, чтобы никто не сел на чужое место и все были довольны маршрутом.
Сложность в том, что программировать решение такого задания можно разве что в мире фантазий: тут важна интуиция и бумага (да-да, именно она – ваш лучший друг). Ведь если пытаться написать программу для этого прямо во время экзамена… ну скажем так: программистам стоит взять отпуск.
Давайте посмотрим на одно из заданий. Есть у нас десять букв: А, B, C… аж до Z (ну почти).
Каждая буква уже частично заняла своё место в автобусе-коде. Например буква B хочет сесть на свободное место с кодом «1000», но нужно проверить условие Фано – чтобы никто не сидел рядом с ней слишком близко (иначе путаница!). И вот после всех проверок оказывается: именно «1000» – идеальный билетик для буквы B!
Можно сказать: «Буква B получила свой VIP-билет!» В ответ пишем просто «1000» — всё гениальное просто.
Или вот другая история про букву А из набора русских букв: А хочет попасть на свободное место «10». Все остальные места заняты или запрещены правилами Фано — своего рода строгим кондуктором автобуса кодов. Так что А спокойно занимает своё место под номером 10 и наслаждается поездкой.
А теперь представьте такую ситуацию: четыре буквы – А, Б, В и Г – уже частично распределены по автобусу.
А – сидит у окна (код 0), Б – у прохода (1100), В – около выхода (1000), а Г всё никак не может выбрать себе место! Тут начинается настоящее веселье с поиском свободного листа в двоичном дереве… Как говорил один мой знакомый программист: «Решение задач по информатике похоже на свидание вслепую — никогда не знаешь заранее кого встретишь на конце пути». Но благодаря условию Фано мы точно знаем — никакого двойного бронирования!
В общем-то эти задания напоминают мне старый анекдот про программиста:…