Задание 11: от алфавита к памяти и обратно

Что требуется найти в задании 11

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

Как связаны алфавит и биты на символ

i бит дают 2ⁱ различных кодов. Для алфавита мощности K выбираем минимальное целое i с условием 2**i ≥ K. Если 4096 кодов уже заняты, ещё один символ требует дополнительного бита.

Для алфавитов с K ≥ 2 диапазон, соответствующий ровно i битам, задаётся так:

Отсюда минимальное K = 2**(i−1) + 1, а максимальное K = 2**i. Эти формулы выбирают разные концы одного диапазона.

Где именно округлять байты

Номер длиной L при i битах на символ содержит L · i бит. Если под каждый номер выделяется целое количество байт, нужно округлить один номер вверх до байта, затем умножить на количество номеров.

Для положительных целых величин в Python это B = (L * i + 7) // 8. Если L · i делится на 8, лишний байт не прибавляется.

Пример: три номера по 9 бит

Один номер: 9 / 8 = 1,125 байта → выделяем 2 байта. Три номера занимают 6 байт. Если сложить 27 бит всех номеров и округлить только один раз, получится 4 байта — такая общая упаковка не соответствует условию отдельного хранения.

В Мбайты переводим уже общий объём в байтах: V / 1024**2. Дополнительное округление Мбайтов делают только по требованию вопроса.

Определи тип до вычислений

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

Найти общий объём памяти

Шаг 1. Собери общий алфавит

В семнадцатеричной системе 17 разных цифр. Поэтому K = 17 + 4080 = 4097.

Шаг 2. Выбери число бит

2¹² = 4096 < 4097, а 2¹³ = 8192 ≥ 4097. Нужно i = 13 бит на символ.

Шаг 3. Округли один номер до байта

257 · 13 = 3341 бит. Делим на 8: 417,625 байта → 418 байт на номер.

Шаг 4. Посчитай все номера

Число номеров равно 8 · 1024², поэтому после перевода в Мбайты остаётся 418 · 8.

alphabet = 17 + 4080
bits = 0
while 2 ** bits < alphabet:
    bits += 1
bytes_per_id = (257 * bits + 7) // 8
total_bytes = bytes_per_id * 8388608
print(total_bytes // (1024 ** 2))  # здесь результат — целое число Мбайт

Найти минимальную мощность алфавита

Шаг 1. Запиши ограничение на всю память

Ищем первые целые i бит, при которых это неравенство выполнено. В шпаргалке деление 12 · 1024² · 8 / 94 523 / 204 ≈ 5,222 даёт ориентир. Окончательно проверяем хранение в целых байтах.

Шаг 2. Возьми минимальный алфавит для 6 бит

Пять бит вмещают 32 символа. Чтобы понадобился шестой бит, нужен хотя бы 33-й символ.

length = 204
count = 94523
limit_bytes = 12 * 1024 ** 2
bits = 1
while ((length * bits + 7) // 8) * count < limit_bytes:
    bits += 1
min_alphabet = 2 ** (bits - 1) + 1
print(min_alphabet)

Цикл в коде продолжается, пока объём ещё меньше 12 Мбайт. Он заканчивается на первых битах, для которых условие «не менее» уже выполнено.

Найти максимальную мощность алфавита

Шаг 1. Сохрани строгое неравенство

Ориентир из деления — примерно 8,145 бита. Проверяем 8 и 9 с округлением каждого номера до байта:

Шаг 2. Возьми верхний конец допустимого алфавита

Последняя подходящая глубина i = 8. При ней можно использовать до 2⁸ символов.

length = 124
count = 124587
limit_bytes = 15 * 1024 ** 2
bits = 0
while ((length * (bits + 1) + 7) // 8) * count < limit_bytes:
    bits += 1
max_alphabet = 2 ** bits
print(max_alphabet)

Почему одной дробной оценки бит недостаточно

Деление общего лимита битов на число символов удобно для оценки. Но оно не учитывает свободные биты в округлённых байтах каждого номера. Поэтому общий объём нужно проверять по точной формуле ((L * i + 7) // 8) * n.

Возьмём два номера длиной по 3 символа. Посмотрим, сколько они занимают при разных i:

Теперь одна таблица даёт три разных ответа:

Подбери i и выбери нужную границу алфавита

Выбери условие и меняй число бит на символ. Смотри, сколько байт выделяется на номер, выполняется ли ограничение и какой диапазон алфавита соответствует этим битам. Затем введи итоговую мощность алфавита.

Двенадцать упражнений на память и алфавит

Проверяй, где округлить байты и какой конец диапазона алфавита нужен. После ошибки можно изменить ответ.

Решено: 0 из 12

Проверка перед ответом

• Мощность алфавита включает все разные символы, в том числе цифры указанной системы счисления.
• Для i бит выполнено 2ⁱ ≥ K, а меньшего числа бит недостаточно.
• Байты округлены вверх отдельно для каждого номера.
• Количество номеров применено после округления одного номера.
• Слова «менее», «не более», «больше», «не менее» переведены в точные знаки сравнения.
• При обратном поиске проверены подходящее и соседнее неподходящее число бит.
• Если спрашивают алфавит, в ответе записано K, а не i.
• Для минимума выбран 2**(i−1)+1, для максимума — 2**i.

Программы с точным байтовым подсчётом