Задание №11. Короткий конспект
Алфавит, биты на символ, байты на запись и проверка границ в задачах об идентификаторах.
Порядок расчёта: разрешённые символы → биты на символ → байты на номер → объём всех записей. Округление выполняется для того объекта, которому условие выделяет целые байты.
Формулы и обозначения
A — мощность алфавита; i — бит на символ; L — символов в номере; n — количество записей; D — дополнительные байты на запись.
| Величина | Правило |
|---|---|
| Бит на символ | Наименьшее целое i с 2^i\ge A |
| Код номера, бит | Li |
| Номер, байт | B=\lceil Li/8\rceil |
| Все записи, байт | V=n(B+D) |
| Сведения, байт | D=V/n-B |
Округление вверх обозначается \lceil x\rceil. Если дополнительных сведений нет, D=0.
1\text{ байт}=8\text{ бит}; 1\text{ Кбайт}=1024\text{ байта}; 1\text{ Мбайт}=1024^2\text{ байт}; 1\text{ Гбайт}=1024^3\text{ байт}.
Обратные задачи
- Длина номера. При известном алфавите сначала определяется i. Затем выбирается целая длина L, для которой общий объём с округлением выполняет условие.
- Мощность алфавита. Сначала находится допустимое i. Для минимального кода длиной i\ge1 выполняется 2^{i-1}<A\le2^i. Нижняя целая граница — 2^{i-1}+1, верхняя — 2^i.
- Минимум или максимум. Найденное значение подставляется в исходный расчёт. Для минимума предыдущее допустимое целое уже не подходит, для максимума — следующее.
Возможные ловушки
- Пропущен регистр или вид символов. В EGE-11-0047 ↗ полный алфавит: 10+26+26+6=68. Пропуск строчных букв занижает число бит с 7 до 6.
- Округлены символы или общий объём. В EGE-11-0026 ↗ 92 бита пароля требуют 12 байт. Округление каждого символа завысит память, объединение свободных битов разных паролей — занизит. При отдельном хранении сначала округляется один номер, затем выполняется умножение на n.
- Потеряно равенство границе. В EGE-11-0005 ↗ «более» исключает равенство; в EGE-11-0003 ↗ «не менее» его допускает. Подмена знака может изменить минимальный ответ; сравнение выполняется в одинаковых единицах.
- Число бит принято за размер алфавита. В EGE-11-0003 ↗ 6 бит соответствуют диапазону 33–64 символа. Для минимума нужен ответ 33, а не 6 или 64.