Обратный ход: мощность алфавита

Спрашивают про алфавит

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

Тот же спуск, последний шаг другой

Объём, байты на код, биты на код, биты на один символ — всё как в прошлой тетради.

А дальше переход от бит к мощности. Максимум — степень двойки, минимум — плюс один.

Если на символ хватает i бит, самый богатый алфавит — ровно 2ⁱ символов.

Если i бит уже мало и нужно i + 1, самый бедный такой алфавит — 2ⁱ + 1 символ. Один лишний символ и ломает границу.

Разбор: серийный номер из 257 символов

Досрочный экзамен 2025 года. Номер — 257 символов, для 295 740 номеров отведено не более 33 Мбайт. Какова наибольшая возможная мощность алфавита?

33 Мбайта — это 34 603 008 байт. На один номер приходится не больше 117 байт.

117 байт — 936 бит. Делим на 257 символов: 3 бита на символ, до четырёх не дотягивает.

Три бита — значит алфавит не больше 2³ = 8 символов.

Программа печатает:

117
936
3
8

Проверка соседа

Наращиваем биты на символ, пока база помещается. Вторая и третья строки — объём при трёх и при четырёх битах, четвёртая — сам лимит.

Программа печатает:

3
28686780
38150460
34603008

Проверь себя

Ловушки

• В ответ записали число бит вместо мощности алфавита.
• В задаче на минимум взяли 2ⁱ вместо 2ⁱ + 1.
• Мегабайты перевели через 1000.
• Не проверили, что соседнее число бит уже не проходит.