Разборы · ЕГЭ, задание 11

Задание 11 ЕГЭ по информатике: информационный объём и мощность алфавита

Что проверяет задание

В задании 11 речь о хранении паролей, номеров, идентификаторов: символы кодируются одинаковым минимальным числом бит, а каждая запись занимает целое число байт. Нужно найти объём памяти, длину записи или, как в демоверсии, наибольшую мощность алфавита. 1 балл.

Что нужно знать

• Для алфавита из N символов нужно i = ⌈log₂N⌉ бит на символ. Наоборот, i битами можно закодировать до 2ⁱ символов.
• Запись из L символов занимает L · i бит, а в байтах — ⌈L · i / 8⌉ (округление вверх: запись хранится целым числом байт).
• Объём для K записей — K · ⌈L · i / 8⌉ байт. 1 Кбайт = 1024 байта.

Как решать

1. Выпишите, что дано: длину записи, число записей, объём памяти, алфавит.
2. Посчитайте бит на символ и байт на запись с правильным округлением.
3. Если нужно найти наибольшее или наименьшее значение, переберите его в цикле — так надёжнее, чем решать неравенства вручную.

Пример из демоверсии 2027

Серийный номер состоит из 157 символов. На каждый номер отводится одинаковое минимальное целое число байт, символы кодируются одинаковым минимальным числом бит. Для 12 450 номеров отведено не более 955 Кбайт. Найдите максимально возможную мощность алфавита.

Решение. На один номер можно потратить не больше 955 · 1024 / 12 450 ≈ 78,5 байта, то есть 78 байт = 624 бита. На символ — не больше 624 / 157 ≈ 3,97 бита, то есть 3 бита. Проверка: при 3 битах номер занимает ⌈471 / 8⌉ = 59 байт — помещается; при 4 битах — ⌈628 / 8⌉ = 79 байт, а 12 450 · 79 = 983 550 байт больше 977 920 — не помещается. Тремя битами кодируется до 2³ = 8 символов.

import math

best = 0
for power in range(2, 1000):
    bits = math.ceil(math.log2(power))          # бит на символ
    per_number = math.ceil(157 * bits / 8)      # байт на номер
    if 12450 * per_number <= 955 * 1024:
        best = power
print(best)                                     # 8

Типичные ошибки

• Округляют байты на запись вниз или не округляют вовсе — запись всегда занимает целое число байт, с запасом.
• Считают 1 Кбайт = 1000 байт.
• Путают, что ищут: мощность алфавита (8) или число бит на символ (3).
• Считают объём всех записей в битах и лишь потом переводят в байты — так теряется округление для каждой записи.

Потренироваться: задание 11 новые варианты с проверкой ответа