Решение: Длина серийного номера
На предприятии каждой изготовленной детали присваивают серийный номер, содержащий десятичные цифры и символы из 15-символьного специального алфавита. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 947 серийных номеров необходимо более 6 Кбайт памяти. Определите минимально возможную длину серийного номера.
Решение по шагам
4 шагаАлфавит серийного номера содержит 10 десятичных цифр и 15 специальных символов, всего 25 символов.
$$10 + 15 = 25$$Минимальное одинаковое число бит для кодирования одного символа находим по формуле Хартли.
$$i = \lceil\log_2 25\rceil = 5$$Для серийного номера длины $n$ требуется $5n$ бит, то есть $\left\lceil\frac{5n}{8}\right\rceil$ байт. Для хранения 947 номеров объём должен быть больше 6 Кбайт.
$$947 \cdot \left\lceil\frac{5n}{8}\right\rceil > 6 \cdot 1024$$При 6 байтах на один номер общий объём равен $947 \cdot 6 = 5682$ байта, что не превышает 6144 байта. Следующее возможное значение — 7 байт; оно достигается при $n=10$.
$$\left\lceil\frac{5 \cdot 10}{8}\right\rceil = 7$$Где здесь ошибаются
Не учитывать округление числа бит до целого при кодировании символа.
Забывать, что каждый серийный номер занимает целое число байт.
Использовать 1000 байт вместо 1024 байт в одном Кбайте.