Решение: Мощность алфавита серийных номеров
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 3 845 627 серийных номеров требуется не менее 11 Гбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров.
Решение по шагам
4 шагаПереведём объём памяти в байты и найдём минимальный объём на один серийный номер:
$$\left\lceil \frac{11 \cdot 2^{30}}{3\,845\,627} \right\rceil = 3072\text{ байта}$$Пусть один символ кодируется $k$ битами. Тогда длина серийного номера в байтах равна:
$$\left\lceil \frac{2783k}{8} \right\rceil$$Требуемый объём достигается при минимальном целом $k$, для которого:
$$\left\lceil \frac{2783k}{8} \right\rceil \ge 3072 \quad \Rightarrow \quad k=9$$При 8 битах можно закодировать не более $2^8=256$ символов. Чтобы для кодирования потребовалось 9 бит, мощность алфавита должна быть минимально равна:
$$2^8+1=257$$Где здесь ошибаются
Забывают округлить объём одного серийного номера вверх до целого числа байт.
Считают, что при 9 битах мощность алфавита обязательно равна $2^9$.
Используют десятичные, а не двоичные гигабайты.