Ах, эти загадочные пароли и байты! Каждый раз, когда слышу слово «пароль», вспоминаю анекдот: «— Почему ты всегда ставишь пароль из девяти символов?
— Потому что десять — это уже перебор!» Ну, а если серьёзно, то давайте вместе погрузимся в мир кодирования и минимизации памяти. Представьте, что вы — системный администратор, который пытается уместить всю информацию о пользователях в крохотный уголок памяти. И тут начинается настоящее веселье с битами и байтами!
Начнём с первого кейса: у нас есть 11 символов – В, У, З, Н, А, Б, Ю, Д, Ж, Е и Т.
Не спрашивайте меня почему именно эти буквы – видимо, кто-то решил сделать алфавит по принципу «всяк символ на вес золота». Пароль состоит из 9 таких символов. Теперь представьте: каждый пользователь получает свой уникальный код – не просто пароль, а настоящий шифр!
И при этом на каждого пользователя выделяется одинаковое количество байт для хранения как пароля, так и дополнительных сведений. Когда в базе оказалось аж 23 пользователя и заняли они целых 713 байт памяти – даже компьютер задумался: «Ну вы даёте!»
Задача стоит такая: сколько же байт отведено под дополнительные данные одного пользователя? Тут я вспомнил старую шутку из IT-среды: «Если хочешь узнать размер своих данных – загляни в глаза своему компьютеру». Но мы не будем гадать на кофейной гуще!
Сначала определим минимальное количество бит для одного символа пароля. Ведь всего-то 11 вариантов – значит хватит логарифма по основанию 2 от 11. Это примерно 3.46 бита (ну или округлим до 4 бит для простоты).
Значит один пароль из 9 символов требует около 36 бит (9 умножить на 4), что равно примерно 4.5 байтам (помните — в одном байте ровно восемь бит). Ну а поскольку память выделяется целыми байтами — значит минимум 5 байт на пароль.
Теперь внимание — общее количество памяти на одного пользователя это сумма памяти под пароль (5 байт) и дополнительные сведения (пусть это будет x байт). Всего пользователей — 23; итого: \(23 \times (5 + x) = 713\). Отсюда \(115 + 23x = 713\), значит \(23x = 598\), следовательно \(x = \frac{598}{23} = 26\) байт!
Вот так просто! Дополнительные сведения занимают целых двадцать шесть байтов — почти как маленький котёнок весом!
Переходим ко второму заданию — здесь уже посерьёзнее: пароль из пятнадцати символов с латинскими буквами верхнего и нижнего регистра плюс цифры. Всего букв латинского алфавита по верхнему регистру – двадцать шесть; нижний регистр тоже двадцать шесть; цифры десять; итого \(26 + 26 +10=62\) варианта символа.
Снова берём логарифм по основанию два от числа вариантов — приблизительно \(log_2(62) \approx 5.95\) бита на символ.
Умножаем на пятнадцать символов пароля — получаем около \(89.25\) бит или приблизительно \(12\) с половиной байта (помним про округление вверх!). В задаче сказано про хранение информации о семнадцати пользователях и всего затрачено двести пятьдесят пять байт.
Если обозначим дополнительные сведения за y бит на пользователя (нам нужно именно биты), то общая память равна:
\[17 \times (\text{пароль в байтах} + \frac{y}{8}) =255.\]
Подставляя значение пароля:
\[17 \times (13 + \frac{y}{8})=255.\]
Отсюда:
\[221 + \frac{17y}{8} =255,\]
то есть
\[\frac{17y}{8}=34,\]
следовательно
\[y=\frac{34 \times8}{17} =16.\]
Вот вам и ответ: для хранения дополнительных сведений нужно выделить ровно шестнадцать бит! Это даже меньше чем длина одного слова «байтик» в нашей кухонной терминологии.