Ах, эти загадочные 11-е задания ЕГЭ по информатике!
Они как те загадочные родственники на семейных сборах: вроде и знаешь, что они есть, но понять их логику — задача не из простых. В прошлой статье мы уже начали разбираться с формулами для объёма текстового сообщения и научились вычислять длину серийных номеров, словно детективы, раскрывающие тайны цифрового мира.
А теперь настала очередь второй части — где нам предстоит определить объём памяти для хранения серийных номеров и идентификаторов. Кто бы мог подумать, что хранить цифры и буквы может быть таким сложным делом!
Представьте себе: у вас есть идентификатор длиной 317 символов, который состоит из десятичных цифр и каких-то загадочных 4090 специальных символов. Это как если бы вы пытались запомнить номер телефона друга, в котором кроме привычных цифр есть ещё и древние руны из Средневековья. И вот вам надо вычислить, сколько памяти займёт целая армия таких идентификаторов — ровно 262 144 штуки!
Число знакомое? Да-да, это же 2 в пятнадцатой степени — прямо как количество злобных боссов в игре, которых вам предстоит победить.
Начинаем с определения мощности нашего алфавита: 10 обычных цифр плюс 4090 спецсимволов — итого 4100 символов.
Казалось бы, простая математика, но тут вспоминается анекдот: «Программист решил посчитать мощность алфавита… и забыл про битовую арифметику». Ведь ближайшая степень двойки к 4100 — это 2 в двенадцатой степени (4096), но она чуть-чуть не дотягивает до нужного количества символов. Значит, придётся брать на один бит больше — тринадцать бит на символ!
Как говорится, чуть больше памяти — зато без сюрпризов.
Длина идентификатора у нас фиксирована — 317 символов. Перемножаем количество бит на длину и переводим в байты (а потом округляем вверх), получаем вес одного идентификатора равный примерно 516 байтам. Теперь представьте себе огромный склад данных с полмиллиона таких маленьких коробочек!
Умножаем на количество идентификаторов — и получаем внушительный объём памяти в мегабайтах: ровно 129 Мбайт. Вот так просто!
Если кто-то думает, что это слишком скучно и напоминает школьную задачу на скорость счёта — вспомните классическую шутку про программиста: «Сколько нужно программистов чтобы заменить лампочку? Ни одного! Это аппаратная проблема».
Здесь же всё наоборот: без чётких формул никак не обойтись.
Переходим к следующему заданию — где каждому пользователю выдаётся пароль длиной всего семь символов из набора строчных латинских букв (26 штук) и десяти арабских цифр. Звучит просто? Но нет! Помимо пароля у каждого пользователя есть ещё дополнительные данные размером в девять байт.
Если бы пароли были пирожками – то дополнительные данные были бы начинкой! Чтобы вычислить общий вес информации о тридцати пользователях придётся опять вспоминать формулы.
Алфавит здесь поменьше: всего 36 символов (буквы + цифры). Ближайшая степень двойки к этому числу – это 2^6 = 64 (а ведь могли взять меньше!), значит каждый символ кодируется шестью битами.
Семь символов по шесть бит дают нам сорок два бита на пароль или пять с половиной байта (снова округляем вверх до шести байт). Добавляем девять байт дополнительных данных – получается пятнадцать байт на пользователя.
Тридцать пользователей умножаем на пятнадцать байт – получаем четыреста пятьдесят байт общего веса информации. И снова программирование приходит нам на помощь со своей точностью и скоростью вычислений!