Базовый (1 балл) Время: 3-5 мин Python как калькулятор bit_length() Округление вверх Все задачи №11 в каталоге

Задание №11. Сколько байт нужно на объект: считаем память

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

В системе хранятся объекты: коды, пароли, блоки данных. Каждый кодируется минимально возможным числом бит, потом округляется до целых байт. Известен общий объём, а надо найти что-то одно, чаще всего дополнительные сведения.

Что от тебя хотят

У каждого объекта в базе есть части: код из символов, блоки с числами, дополнительные сведения. Каждая часть занимает какое-то число байт, а условие часто говорит «минимально возможное целое число байт». В конце дано, сколько памяти заняло много объектов, и нужно найти один неизвестный кусочек.

Четыре правила

Бит на символ. Для алфавита из N символов нужно столько бит i, чтобы выполнялось 2ⁱ ≥ N. В Python это (N - 1).bit_length(). Для 36 символов (26 букв и 10 цифр) получается 6 бит.
Бит на весь код. Умножаем число символов на бит на символ.
Округляем до байт вверх, и ровно там, где сказано. Целое число байт на код: (биты + 7) // 8.
Складываем части, умножаем на число объектов. Общий объём делим на число объектов, чтобы получить размер одного.

Не округляй раньше времени. Если части кодируются каждая в целое число байт, округляй каждую отдельно. Если в условии сказано, что целое число байт отведено на весь объект, округляй один раз в конце.

Разбор 1: код изделия и блоки деталей

Код изделия состоит из 25 символов (заглавные латинские буквы и цифры) и кодируется минимально возможным целым числом байт, посимвольно, все символы одинаковым минимальным числом бит. Для данных о деталях выделено 80 блоков; каждый содержит код детали (число до 1 000 000) и количество (число до 1000) и кодируется минимальным целым числом байт. Для дополнительных сведений выделено одинаковое целое число байт. Для 32 768 объектов потребовалось 11 Мбайт. Сколько байт отведено на дополнительные сведения одного объекта?

Символов 36 (26 + 10), нужно 6 бит. Код: 25 · 6 = 150 бит, это 19 байт.
Блок: код детали 20 бит (2²⁰ = 1 048 576 ≥ 1 000 000), количество 10 бит. Всего 30 бит, это 4 байта. На 80 блоков 320 байт.
На один объект: 11 · 1024 · 1024 / 32768 = 352 байта.
Остаётся на дополнительные сведения: 352 − 19 − 320 = 13 байт.

Первое окно считает ровно по этим шагам.

Разбор 2: пароли и пользователи

Пароль состоит из 15 символов, алфавит содержит 12 букв и 10 цифр. Каждый пароль хранится в минимально возможном целом числе байт, кодирование посимвольное. Ещё на каждого пользователя отведено 6 байт. Сколько байт нужно для 100 пользователей?

Символов 22, бит на символ 5. Пароль 75 бит, это 10 байт. На пользователя 10 + 6 = 16, на сто 1600 байт.

Единицы памяти: 1 Кбайт = 1024 байта, 1 Мбайт = 1024 Кбайта. Если в условии «11 Мбайт», в байты переводи как 11 · 1024 · 1024.

Разновидности и прототипы задания на экзамене

Тип 1: Пароль или код из символов

Алфавит определяет число бит на символ, а длина кода число бит на весь код.

Тип 2: Блоки данных

Блок состоит из нескольких чисел. Для каждого находим биты, складываем, округляем до байта.

Тип 3: Найти дополнительные сведения

Известно, сколько памяти заняли все объекты. Вычитаем всё известное, остаётся искомое.

Код решения на Python

Запустить код в онлайн-песочнице

Дополнительные сведения об изделии

symbol_bits = (36 - 1).bit_length()
code_bytes = (25 * symbol_bits + 7) // 8

part_bits = (1000000 - 1).bit_length() + (1000 - 1).bit_length()
part_bytes = (part_bits + 7) // 8
parts_bytes = 80 * part_bytes

per_object = 11 * 1024 * 1024 // 32768
print(per_object - code_bytes - parts_bytes)

Пароли для сотни пользователей

symbols = 12 + 10
bits = (symbols - 1).bit_length()
password_bytes = (15 * bits + 7) // 8

per_user = password_bytes + 6
print(per_user * 100)

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

✕ Не так

Округлить общий объём, а не каждый пароль

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

✓ Так

Округлять вверх вес каждого пароля отдельно: (15 * i + 7) // 8.

✕ Не так

Брать бит на символ как log2(N) без округления

Для 36 символов log2 даёт 5,17, а бит должно быть целое число.

✓ Так

Округлять вверх: (N - 1).bit_length().

✕ Не так

Забыть, что в Мбайте 1024 · 1024 байта

Считать 1 Мбайт как миллион байт.

✓ Так

1 Мбайт = 1 048 576 байт.

ГРОБ

ГРОБ №11: Дополнительные сведения в битах

В условии сказано, что дополнительные сведения занимают, например, 14 бит, а на весь объект отведено целое число байт.

Как обойти

Тогда округляй один раз для всего объекта сразу: (биты_кода + 14 + 7) // 8. Если же дополнительные сведения заданы целым числом байт, их просто прибавляют к байтам.

Лайфхаки на экзамене

Число бит для N вариантов: (N - 1).bit_length(). Проверка для степеней двойки: для 256 получается 8, для 257 уже 9.
Округление вверх при делении на 8: (биты + 7) // 8, без модуля math.
Нужно найти неизвестное? Сначала посчитай размер одного объекта целиком, потом вычти всё известное.

Банк реальных задач №11 Открыть в тренажере СмартКИМ