Память для паролей и идентификаторов
Пароль или идентификатор хранят посимвольно: каждый символ занимает одинаковое минимальное число бит, а вся запись — целое число байт. Сначала находят мощность алфавита и бит на символ, затем байты на запись с округлением вверх, и только потом умножают на число записей. Обратные задачи ищут байты на дополнительные сведения или наибольшую мощность алфавита при заданном объёме памяти.
Как посчитать память для записей
Запись из символов алфавита мощности хранят в одинаковом минимальном целом числе байт.
- Мощность алфавита — сумма размеров всех наборов символов из условия.
- Бит на символ: наименьшее , при котором .
- Байт на запись: , округление вверх для каждой записи. Дополнительные сведения прибавляют к .
- Память для записей: байт, затем деление на 1024 для Кбайт или на для Мбайт.
- Обратная задача: байт на запись не больше целой части от , отсюда находят и .
Мощность алфавита из нескольких наборов
Если запись составляют из символов нескольких наборов, мощность алфавита равна сумме их размеров. Десятичные цифры — 10 символов, латинские буквы одного регистра — 26, строчные и заглавные вместе — 52. Цифры системы счисления с основанием — это символов: цифр шестнадцатеричной системы 16, семнадцатеричной — 17.
По мощности найдите число бит на символ : наименьшее целое, при котором . Символы кодируют одинаковым числом бит, поэтому общее для всех символов.
Пример
Пароль составляют из десятичных цифр, строчных и заглавных латинских букв. Сколько бит нужно на символ?
- 1..
- 2., значит бит.
Ответ: 6 бит
Целое число байт на одну запись
Запись из символов занимает бит. Под каждую запись отводят одинаковое и минимальное целое число байт, поэтому : разделите на 8 и округлите вверх. Округляют каждую запись отдельно, до умножения на число записей. Если сначала умножить биты на число записей, а округлить в конце, ответ может получиться меньше верного.
Пример
Идентификатор из 15 символов записан алфавитом из 20 символов. Сколько байт займут 100 идентификаторов?
- 1., значит бит.
- 2.Один идентификатор: бит, , округляем вверх: байт.
- 3.100 идентификаторов: байт.
Ответ: 1000 байт
Память для многих записей в Кбайт и Мбайт
Память для записей равна байт. Чтобы получить Кбайт, разделите на 1024, Мбайт — на . Число записей в таких задачах обычно кратно 1024, поэтому деление удобно сократить заранее: .
Программа повторяет шаги: мощность алфавита, бит на символ, байт на запись, память. Округление вверх при делении на 8 записано как (length * i + 7) // 8. Для идентификатора из 317 символов алфавита и записей программа печатает 129.
Пример задания
Открытый банк ФИПИ
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 317 символов и содержащий только десятичные цифры и символы из 4090-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Мбайт), необходимый для хранения 262 144 идентификаторов. В ответе запишите только целое число – количество Мбайт.
Пароль и дополнительные сведения
Иногда для каждого пользователя кроме пароля хранят дополнительные сведения — одинаковое целое число байт . Тогда запись пользователя занимает байт, где — байты на пароль. Память для пользователей равна байт.
Пример
Пароль из 11 символов составляют из 30-символьного алфавита. Для каждого пользователя хранят ещё 13 байт сведений. Сколько байт нужно на 50 пользователей?
- 1., значит бит.
- 2.Пароль: бит, , округляем вверх: 7 байт.
- 3.Пользователь: байт. 50 пользователей: байт.
Ответ: 1000 байт
Как найти байты на дополнительные сведения
Если известна память байт для пользователей, на одного пользователя приходится байт. Из них байт занимает пароль, поэтому на дополнительные сведения отведено байт. Байты на пароль найдите так же, с округлением вверх.
Пример задания
Открытый банк ФИПИ
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов и содержащий только символы из 26-символьного набора строчных и 26-символьного набора заглавных латинских букв и десяти арабских цифр. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 90 пользователях потребовалось 1800 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число — количество байт.
Наибольшая мощность алфавита при ограниченной памяти
Если для записей отведено не больше байт, на запись приходится не больше байт, где — целая часть от . На символ тогда не больше целой части от бит. Проверьте, что при этом запись помещается: , а при уже нет. Наибольшая мощность алфавита равна .
Программа увеличивает , пока запись с битами на символ ещё помещается в байт. Для примера ниже она печатает 32.
Пример
Серийный номер из 120 символов хранят посимвольно в минимальном целом числе байт. Для 4096 номеров отведено не более 300 Кбайт. Какова наибольшая мощность алфавита?
- 1.На номер: байт.
- 2.На символ: бит.
- 3.Проверка: бит — ровно 75 байт, помещается. С 6 битами нужно 90 байт, не помещается.
- 4.Мощность: .
Ответ: 32