Решение: Минимальная мощность алфавита
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 196 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 564 895 серийных номеров потребовалось не менее 145 Мбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров.
Решение по шагам
4 шагаПереведём минимальный требуемый объём памяти в байты и найдём, сколько байт должно приходиться на один серийный номер.
$$145 \cdot 2^{20}=152043520\text{ байт}$$Делим общий объём на количество серийных номеров. Так как объём должен быть не меньше указанного, требуется не менее 270 байт на один номер.
$$\left\lceil\dfrac{152043520}{564895}\right\rceil=270\text{ байт}$$Пусть один символ кодируется $k$ битами. Тогда один номер занимает $\left\lceil\dfrac{196k}{8}\right\rceil$ байт. Проверяем минимальное подходящее значение: при $k=10$ получаем 245 байт, а при $k=11$ — 270 байт.
$$\left\lceil\dfrac{196\cdot 10}{8}\right\rceil=245,\qquad \left\lceil\dfrac{196\cdot 11}{8}\right\rceil=270$$Чтобы кодировать символы 11 битами, алфавит должен содержать больше $2^{10}$ символов, но не больше $2^{11}$. Минимальная возможная мощность такого алфавита равна $2^{10}+1$.
$$2^{10}+1=1025$$Где здесь ошибаются
Использовать 145000000 байт вместо перевода 145 Мбайт в двоичные байты.
Забыть округлить число байт на один серийный номер вверх.
Взять мощность алфавита равной $2^{11}$ вместо минимального значения $2^{10}+1$.