На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 157 символов.
В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит.
Известно, что для хранения 12 450 серийных номеров отведено не более 955 Кбайт памяти. Определите максимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.
Ответ:
Демонстрационный вариант ЕГЭ 2027 по информатике – задание №11
Решение:
Пусть m — мощность алфавита, то есть количество различных символов, которые могут использоваться в серийном номере.
Количество бит, необходимое для кодирования одного символа:
|
1 |
p = ceil(log2(m)) |
Так как серийный номер состоит из 157 символов, объём одного номера в байтах равен:
|
1 |
n = ceil((157 * p) / 8) |
Для хранения 12 450 серийных номеров должно потребоваться не более 955 Кбайт:
|
1 |
n * 12_450 <= 955 * 1024 |
Переберём возможные значения мощности алфавита:
|
1 2 3 4 5 6 7 8 9 |
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. Максимальное из них:
|
1 |
8 |
Проверим.
Для алфавита из 8 символов:
ceil(log28) = 3 бита
На один серийный номер требуется:
ceil(157 · 3 / 8) = ceil(58,875) = 59 байт.
Для 12 450 номеров:
59 · 12 450 = 734 550 байт,
что не превышает:
955 · 1024 = 977 920 байт.
При увеличении мощности алфавита до 9 для кодирования одного символа уже потребуется 4 бита, и объём памяти превысит допустимый.
Ответ: 8