Решение: Мощность алфавита номера
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 124 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 124 587 серийных номеров отведено менее 15 Мбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров.
Решение по шагам
5 шаговПусть на кодирование одного символа отводится $b$ бит. Тогда мощность алфавита не превышает $2^b$.
При $b=8$ один серийный номер занимает $124 \cdot 8 = 992$ бита, то есть $124$ байта.
Общий объём памяти для 124 587 номеров при $b=8$ равен $124\,587 \cdot 124 = 15\,448\,788$ байт, что меньше $15 \cdot 2^{20} = 15\,728\,640$ байт.
При $b=9$ один номер занимает $\left\lceil \dfrac{124 \cdot 9}{8} \right\rceil = 140$ байт. Тогда общий объём равен $124\,587 \cdot 140 = 17\,442\,180$ байт, что превышает отведённый объём.
Следовательно, максимально возможное число бит на символ равно 8, а мощность алфавита равна $2^8 = 256$.
Где здесь ошибаются
Сравнивают объём в байтах с 15 без перевода мегабайт в байты.
Забывают округлить объём одного номера до целого числа байт.
Используют $2^9$ вместо проверки ограничения по общему объёму памяти.