ГДЗ 181) На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 251 символов. В базе дан...
181)
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 251 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимальным числом бит. Известно, что для хранения 65 536 серийных номеров потребовалось не менее 8064 Кбайт памяти. Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.
Решение:
-
Найдём объём памяти, отводимый на один серийный номер ($I_{номер}$): Общий объём памяти $I_{общий} \ge 8064$ Кбайт. Переведём это значение в байты:
$$ 8064 \text{ Кбайт} = 8064 \cdot 1024 \text{ байт} $$Количество номеров $N = 65\,536 = 2^{16}$.
$$ I_{номер} = \frac{I_{общий}}{N} \ge \frac{8064 \cdot 1024}{65536} = \frac{8064 \cdot 2^{10}}{2^{16}} = \frac{8064}{2^6} = \frac{8064}{64} = 126 \text{ байт} $$Так как по условию каждый номер занимает минимально возможное целое число байт, и общий объём не менее 8064 Кбайт, принимаем $I_{номер} = 126$ байт.
-
Определим количество бит на один символ ($i$): Длина номера $L = 251$ символ. Объём в битах для одного номера должен быть не более $126 \cdot 8 = 1008$ бит, но более $125 \cdot 8 = 1000$ бит (иначе номер занимал бы 125 байт или меньше).
$$ 1000 < 251 \cdot i \le 1008 $$Проверим целые значения $i$:
- Если $i = 4$, то $251 \cdot 4 = 1004$ бита. Условие $1000 < 1004 \le 1008$ выполняется. Следовательно, на кодирование одного символа отводится $i = 4$ бита.
-
Найдём мощность алфавита ($M$): Количество бит $i$ связано с мощностью алфавита $M$ формулой Хартли: $2^{i-1} < M \le 2^i$. Для $i = 4$ получаем:
$$ 2^3 < M \le 2^4 \Rightarrow 8 < M \le 16 $$Минимально возможная мощность алфавита, при которой для кодирования одного символа требуется именно 4 бита, равна 9.
Ответ: 9