При регистрации в компьютерной системе каждому объекту...

Задание

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 257 символов и содержащий только цифры семнадцатеричной системы счисления и символы из 4080-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит. Определите объём памяти (в Мбайт), необходимый для хранения 8 388 608 идентификаторов.

Решение

Разбор кода. Сначала считаем общее количество различных символов в алфавите: 17 цифр семнадцатеричной системы плюс 4080 символов специального алфавита, итого N = 17 + 4080. По формуле Хартли мощность алфавита связана с длиной кода одного символа: 2i ≥ N, откуда i = ceil(log2(N)) — минимальное целое число бит на один символ.

Затем находим объём одного идентификатора в байтах. Длина идентификатора 257 символов, значит, всего 257 * i бит. Делим на 8 и округляем вверх: v = ceil(257 * i / 8) — это минимальное целое число байт, которое отводится под один идентификатор.

Умножаем v на количество идентификаторов 8 388 608 и переводим байты в мегабайты, деля на 2**20 = 1 048 576.

Ключевой момент: округление вверх делается дважды и по разным причинам. Первый раз — при подсчёте бит на символ (мощность алфавита не обязана быть степенью двойки). Второй раз — при переводе бит в байты, потому что под идентификатор отводится целое число байт, и «недостающий» бит тоже занимает целый байт.

Ответ: 3344