Решение: Длина серийного номера
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 52 латинские буквы с учётом регистра и символы из 458-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров: все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 862 серийных номеров отведено не более 276 Кбайт памяти. Определите максимально возможную длину серийного номера.
Решение по шагам
5 шаговОпределим количество символов в алфавите серийного номера:
$$10 + 52 + 458 = 520$$Минимальное одинаковое число бит на один символ должно удовлетворять условию $2^i \geq 520$:
$$i = \lceil \log_2 520 \rceil = 10$$Серийный номер длиной $L$ символов занимает $10L$ бит, то есть $\left\lceil \dfrac{10L}{8} \right\rceil$ байт. Общий объём памяти не должен превышать $276$ Кбайт:
$$862 \cdot \left\lceil \dfrac{10L}{8} \right\rceil \leq 276 \cdot 1024$$Максимальный допустимый размер одного номера равен 327 байтам, так как $862 \cdot 327 = 281874$, а $862 \cdot 328 = 282736 > 276 \cdot 1024 = 282624$.
$$\left\lceil \dfrac{10L}{8} \right\rceil \leq 327$$Проверяем длину $L=261$: номер занимает $\left\lceil \dfrac{10 \cdot 261}{8} \right\rceil = \lceil 326{,}25 \rceil = 327$ байт. Длина $262$ потребовала бы 328 байт и не满足 ограничению.
$$L_{\max}=261$$Где здесь ошибаются
Используют 9 бит для символа, хотя $2^9 < 520$.
Забывают округлить размер одного серийного номера вверх до целого числа байт.
Используют 1 Кбайт = 1000 байт вместо 1024 байт.