Сотрудникам компании выдают электронную карту, на которой записан их идентификатор, состоящий из двух частей. Первая содержит 12 символов и может включать латинские буквы…
Сотрудникам компании выдают электронную карту, на которой записан их идентификатор, состоящий из двух частей. Первая содержит 12 символов и может включать латинские буквы (заглавные и строчные) и десятичные цифры. Для хранения кода используется посимвольное кодирование, на каждый символ отводится одинаковое минимально возможное количество бит. Вторая часть — целое число от 1 до 1117, для его кодирования используется одинаковое и минимально возможное целое число бит. Для кодирования всего идентификатора выделяется целое число байт. Кроме того, на электронной карте каждого пользователя хранятся дополнительные сведения, которые занимают 20 байт. Определите максимальное число пользователей, данные которых можно сохранить с помощью 2 Кбайт памяти.
Ответ: 66 сотрудников.
Пошаговое решение
- Первая часть идентификатора
- Разрешенные символы: латинские буквы (26 заглавных + 26 строчных) и цифры (10) = 62 символа.
- Минимальное количество бит на символ: ceil(log2(62)) = 6 бит.
- Длина первой части: 12 символов.
- Биты для первой части: 12 × 6 = 72 бит.
- Вторая часть идентификатора
- Значения: от 1 до 1117 (1117 различных значений).
- Необходимо минимальное число бит k, такое что 2^k ≥ 1117 → k = ceil(log2(1117)) = 11 бит.
- Всего для идентификатора
- Всего бит: 72 + 11 = 83 бит.
- Перевод в байты: нужно целое число байт, чтобы сохранить 83 бита → ceil(83/8) = 11 байт.
- Дополнительные сведения
- На карту каждого сотрудника занимают 20 байт.
- Память под одного пользователя
- Всего под одного пользователя: 11 байт (идентификатор) + 20 байт (доп. данные) = 31 байт.
- Максимальное число пользователей
- Доступная память: 2 Кбайт = 2048 байт.
- Максимальное число пользователей: floor(2048 / 31) = 66.
- Остаток памяти: 2048 − 66 × 31 = 2 байта (недостаточно для еще одного пользователя).
Итого: можно сохранить максимум 66 пользователей.
