Решение: Мощность алфавита серийных номеров
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 172 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 187 564 серийных номеров отведено не более 39 Мбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров.
Решение по шагам
5 шаговПусть один символ кодируется $i$ битами. Тогда максимальная мощность алфавита при таком кодировании равна $2^i$.
При $i = 10$ длина одного номера составляет $172 \cdot 10 = 1720$ бит, то есть минимально необходимое целое число байт равно $\left\lceil 1720/8 \right\rceil = 215$ байт.
Объём памяти для всех номеров при $i = 10$: $187564 \cdot 215 = 40326260$ байт. Допустимый объём равен $39 \cdot 2^{20} = 40894464$ байт, поэтому условие выполняется.
При $i = 11$ на один номер потребуется $\left\lceil 172 \cdot 11/8 \right\rceil = 237$ байт, а общий объём $187564 \cdot 237 = 444?$. Этот объём превышает $39 \cdot 2^{20}$ байт, поэтому 11 бит использовать нельзя.
Следовательно, максимальное число бит на символ равно 10, а мощность алфавита равна $2^{10} = 1024$.
Где здесь ошибаются
Не округляют объём одного серийного номера вверх до целого числа байт.
Сравнивают объём в байтах с числом 39, не переводя Мбайт в байты.
Берут $2^{11}$ как ответ, хотя 11 бит на символ не укладываются в ограничение по памяти.