Задание 11
тема 1 из 2

Память для паролей и идентификаторов

Пароль или идентификатор хранят посимвольно: каждый символ занимает одинаковое минимальное число бит, а вся запись — целое число байт. Сначала находят мощность алфавита и бит на символ, затем байты на запись с округлением вверх, и только потом умножают на число записей. Обратные задачи ищут байты на дополнительные сведения или наибольшую мощность алфавита при заданном объёме памяти.

Главная тема в задании11На карте навыков

Как посчитать память для записей

Запись из LL символов алфавита мощности NN хранят в одинаковом минимальном целом числе байт.

  • Мощность алфавита NN — сумма размеров всех наборов символов из условия.
  • Бит на символ: наименьшее ii, при котором 2i≥N2^i \ge N.
  • Байт на запись: b=⌈L⋅i8⌉b = \left\lceil \dfrac{L \cdot i}{8} \right\rceil, округление вверх для каждой записи. Дополнительные сведения прибавляют к bb.
  • Память для nn записей: n⋅bn \cdot b байт, затем деление на 1024 для Кбайт или на 2202^{20} для Мбайт.
  • Обратная задача: байт на запись не больше целой части от Vn\dfrac{V}{n}, отсюда находят ii и N=2iN = 2^i.

Мощность алфавита из нескольких наборов

Если запись составляют из символов нескольких наборов, мощность алфавита равна сумме их размеров. Десятичные цифры — 10 символов, латинские буквы одного регистра — 26, строчные и заглавные вместе — 52. Цифры системы счисления с основанием PP — это PP символов: цифр шестнадцатеричной системы 16, семнадцатеричной — 17.

По мощности NN найдите число бит на символ ii: наименьшее целое, при котором 2i≥N2^i \ge N. Символы кодируют одинаковым числом бит, поэтому ii общее для всех символов.

Пример

Пароль составляют из десятичных цифр, строчных и заглавных латинских букв. Сколько бит нужно на символ?

  1. 1.N=10+26+26=62N = 10 + 26 + 26 = 62.
  2. 2.25=32<62≤64=262^5 = 32 < 62 \le 64 = 2^6, значит i=6i = 6 бит.

Ответ: 6 бит

Целое число байт на одну запись

Запись из LL символов занимает L⋅iL \cdot i бит. Под каждую запись отводят одинаковое и минимальное целое число байт, поэтому b=⌈L⋅i8⌉b = \left\lceil \dfrac{L \cdot i}{8} \right\rceil: разделите на 8 и округлите вверх. Округляют каждую запись отдельно, до умножения на число записей. Если сначала умножить биты на число записей, а округлить в конце, ответ может получиться меньше верного.

Пример

Идентификатор из 15 символов записан алфавитом из 20 символов. Сколько байт займут 100 идентификаторов?

  1. 1.24=16<20≤32=252^4 = 16 < 20 \le 32 = 2^5, значит i=5i = 5 бит.
  2. 2.Один идентификатор: 15⋅5=7515 \cdot 5 = 75 бит, 75:8=9,37575 : 8 = 9{,}375, округляем вверх: b=10b = 10 байт.
  3. 3.100 идентификаторов: 100⋅10=1000100 \cdot 10 = 1000 байт.

Ответ: 1000 байт

Память для многих записей в Кбайт и Мбайт

Память для nn записей равна n⋅bn \cdot b байт. Чтобы получить Кбайт, разделите на 1024, Мбайт — на 220=1 048 5762^{20} = 1\,048\,576. Число записей в таких задачах обычно кратно 1024, поэтому деление удобно сократить заранее: 262 144=218262\,144 = 2^{18}.

Программа повторяет шаги: мощность алфавита, бит на символ, байт на запись, память. Округление вверх при делении на 8 записано как (length * i + 7) // 8. Для идентификатора из 317 символов алфавита 10+409010 + 4090 и 262 144262\,144 записей программа печатает 129.

Пример задания

Открытый банк ФИПИ

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 317 символов и содержащий только десятичные цифры и символы из 4090-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Мбайт), необходимый для хранения 262 144 идентификаторов. В ответе запишите только целое число – количество Мбайт.

Пароль и дополнительные сведения

Иногда для каждого пользователя кроме пароля хранят дополнительные сведения — одинаковое целое число байт ee. Тогда запись пользователя занимает b+eb + e байт, где bb — байты на пароль. Память для nn пользователей равна n⋅(b+e)n \cdot (b + e) байт.

Пример

Пароль из 11 символов составляют из 30-символьного алфавита. Для каждого пользователя хранят ещё 13 байт сведений. Сколько байт нужно на 50 пользователей?

  1. 1.24=16<30≤32=252^4 = 16 < 30 \le 32 = 2^5, значит i=5i = 5 бит.
  2. 2.Пароль: 11⋅5=5511 \cdot 5 = 55 бит, 55:8=6,87555 : 8 = 6{,}875, округляем вверх: 7 байт.
  3. 3.Пользователь: 7+13=207 + 13 = 20 байт. 50 пользователей: 50⋅20=100050 \cdot 20 = 1000 байт.

Ответ: 1000 байт

Как найти байты на дополнительные сведения

Если известна память VV байт для nn пользователей, на одного пользователя приходится Vn\dfrac{V}{n} байт. Из них bb байт занимает пароль, поэтому на дополнительные сведения отведено e=Vn−be = \dfrac{V}{n} - b байт. Байты на пароль найдите так же, с округлением вверх.

Пример задания

Открытый банк ФИПИ

При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 9 символов и содержащий только символы из 26-символьного набора строчных и 26-символьного набора заглавных латинских букв и десяти арабских цифр. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего выделено целое число байт; это число одно и то же для всех пользователей.
Для хранения сведений о 90 пользователях потребовалось 1800 байт. Сколько байт выделено для хранения дополнительных сведений об одном пользователе? В ответе запишите только целое число — количество байт.

Наибольшая мощность алфавита при ограниченной памяти

Если для nn записей отведено не больше VV байт, на запись приходится не больше BB байт, где BB — целая часть от Vn\dfrac{V}{n}. На символ тогда не больше целой части от 8⋅BL\dfrac{8 \cdot B}{L} бит. Проверьте, что при этом ii запись помещается: ⌈L⋅i8⌉≤B\left\lceil \dfrac{L \cdot i}{8} \right\rceil \le B, а при i+1i + 1 уже нет. Наибольшая мощность алфавита равна 2i2^i.

Программа увеличивает ii, пока запись с i+1i + 1 битами на символ ещё помещается в BB байт. Для примера ниже она печатает 32.

Пример

Серийный номер из 120 символов хранят посимвольно в минимальном целом числе байт. Для 4096 номеров отведено не более 300 Кбайт. Какова наибольшая мощность алфавита?

  1. 1.На номер: 300⋅1024:4096=75300 \cdot 1024 : 4096 = 75 байт.
  2. 2.На символ: 75⋅8:120=575 \cdot 8 : 120 = 5 бит.
  3. 3.Проверка: 120⋅5=600120 \cdot 5 = 600 бит — ровно 75 байт, помещается. С 6 битами нужно 90 байт, не помещается.
  4. 4.Мощность: 25=322^5 = 32.

Ответ: 32

Потренируйте навык

Все задания на этот навык

Решать