Е11.64 Известно, что для хранения 12 450 серийных номеров отведено не более 955 Кбайт памяти

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 157 символов.

В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит.

Известно, что для хранения 12 450 серийных номеров отведено не более 955 Кбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.

Ответ:

Демонстрационный вариант ЕГЭ 2027 по информатике – задание №11

Решение:

Пусть m — мощность алфавита, то есть количество различных символов, которые могут использоваться в серийном номере.

Количество бит, необходимое для кодирования одного символа:

p = ceil(log2(m))

1	p = ceil(log2(m))

Так как серийный номер состоит из 157 символов, объём одного номера в байтах равен:

n = ceil((157 * p) / 8)

1	n = ceil((157 * p) / 8)

Для хранения 12 450 серийных номеров должно потребоваться не более 955 Кбайт:

n * 12_450 <= 955 * 1024

1	n * 12_450 <= 955 * 1024

Переберём возможные значения мощности алфавита:

from math import *

for m in range(1, 10000):
    p = ceil(log2(m))
    n = ceil((157 * p) / 8)

    if n * 12_450 <= 955 * 1024:
        print(m)

from math import *

for m in range(1, 10000):

p = ceil(log2(m))

n = ceil((157 * p) / 8)

if n * 12_450 <= 955 * 1024:

print(m)

Программа выводит все допустимые значения m. Максимальное из них:

8

Проверим.

Для алфавита из 8 символов:

ceil(log₂8) = 3 бита

На один серийный номер требуется:

ceil(157 · 3 / 8) = ceil(58,875) = 59 байт.

Для 12 450 номеров:

59 · 12 450 = 734 550 байт,

что не превышает:

955 · 1024 = 977 920 байт.

При увеличении мощности алфавита до 9 для кодирования одного символа уже потребуется 4 бита, и объём памяти превысит допустимый.

Ответ: 8