Решение: Длина серийного номера
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры, 26 латинских букв (без учёта регистра) и символы из 4070-символьного специального алфавита. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 960 серийных номеров отведено более 212 Кбайт памяти. Определите минимально возможную длину серийного номера.
Решение по шагам
5 шаговОпределим мощность алфавита серийного номера:
$$10 + 26 + 4070 = 4106$$Найдём минимальное одинаковое число бит для кодирования одного символа. Поскольку $2^{12}=4096<4106\leq 2^{13}=8192$, требуется $13$ бит на символ.
$$i=13$$Для серийного номера длины $n$ количество информации равно $13n$ бит, поэтому отведённый объём в байтах равен:
$$b=\left\lceil\frac{13n}{8}\right\rceil$$Память для 960 номеров должна быть больше $212$ Кбайт:
$$960b>212\cdot1024$$Следовательно, на один номер требуется не менее $227$ байт. Проверяем минимальную длину: при $n=140$ получаем $\left\lceil\frac{13\cdot140}{8}\right\rceil=\lceil227{,}5\rceil=228$ байт, а при $n=139$ — $\left\lceil\frac{13\cdot139}{8}\right\rceil=226$ байт. Значит, минимальная длина равна $140$.
$$\left\lceil\frac{13\cdot139}{8}\right\rceil=226,\qquad \left\lceil\frac{13\cdot140}{8}\right\rceil=228$$Где здесь ошибаются
Считать, что для 4106 символов достаточно 12 бит, хотя $4106>2^{12}$.
Не округлять объём одного серийного номера вверх до целого числа байт.
Использовать 1000 байт в одном Кбайте вместо принятого в задаче значения $1024$ байта.