Определение мощности алфавита серийного номера: 31, 261, 252, 500 · ЕГЭ №11

Условие, ответ и разбор задачи

Вычисление количества информации

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 261 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 252 500 серийных номеров отведено более 31 Мбайт памяти. Определите минимально возможную мощность алфавита, из которого составляются серийные номера.

В ответе запишите только число.

Ответ:

Решение

Номер состоит из 261 символа.

Памяти отведено больше 31 Мбайт, значит на один номер больше 31 × 1024 × 1024 / 252500 = 128,74 байт, то есть не меньше 129 байт.

При 3 битах на символ: 261 × 3 = 783 бит = 98 байт — мало.

При 4 битах: 261 × 4 = 1044 бит, 1044 / 8 = 130,5, округляем вверх — 131 байт — подходит.

Четыре бита нужны, начиная с алфавита в 9 символов: 8 символов кодируются тремя битами.

Минимальная мощность алфавита — 9.

Тот же ответ даёт перебор по мощности алфавита:

from math import ceil, log2
for n in range(2, 10000):
    b = ceil(log2(n))
    if 252500 * ceil(261 * b / 8) > 31 * 1024 * 1024:
        print(n)
        break

$\textbf{Ответ: 9.}$

Определение мощности алфавита серийного номера: 31, 261, 252, 500 · ЕГЭ №11

Похожие задачи