В информационной системе хранится информация об объектах определённой структуры. Описание каждого объекта включает в себя идентификатор объекта, описание структуры объекта и…
В информационной системе хранится информация об объектах определённой структуры. Описание каждого объекта включает в себя идентификатор объекта, описание структуры объекта и дополнительную информацию. Идентификатор объекта состоит из 7 заглавных латинских букв. Каждая буква идентификатора кодируется минимально возможным числом битов. Структура объекта описывается как последовательность из 70 простых элементов. Всего существует 1789 различных простых элементов. Каждый простой элемент кодируется одинаковым для всех элементов минимально возможным количеством битов. Для хранения описания каждого объекта выделяется одинаковое для всех объектов минимальное количество байтов, при этом для хранения дополнительной информации выделяется одинаковое для всех объектов целое число байтов. Известно, что для хранения данных о 16384 объектах потребовалось 3 Мбайт. Сколько байтов выделено для хранения дополнительной информации об одном объекте? В ответе запишите целое число количество байт.
Дано задачи:
- Идентификатор состоит из 7 заглавных латинских букв. Для каждой буквы требуется минимальное число бит, чтобы кодировать 26 символов.
- Структура объекта — последовательность из 70 простых элементов; всего 1789 различных элементов. Каждому элементу соответствует одинаковое минимальное число бит.
- Для каждого объекта выделяется минимальное количество байтов под само описание и целое число байтов под дополнительную информацию.
Найти: сколько байтов выделено под дополнительную информацию на один объект.
Решение по шагам:
- Число бит на букву id
- 26 возможных символов → минимально 5 бит (так как 2^4 = 16, 2^5 = 32).
- 7 букв → 7 × 5 = 35 бит.
- Число бит на элемент структуры
- 1789 элементов → минимально 11 бит (так как 2^10 = 1024, 2^11 = 2048).
- 70 элементов → 70 × 11 = 770 бит.
- Общее число бит для описания объекта
- 35 бит (id) + 770 бит (структура) = 805 бит.
- Минимальное число байтов под описание
- 805 бит требуется хранить в байтах: ceil(805 / 8) = ceil(100.625) = 101 байт.
- Обозначим это число как B = 101.
- Обозначим M как количество байтов под дополнительную информацию (целое число).
- Общее число байт на объект: B + M.
- Всего объектов: 16384 = 2^14.
- Объем памяти: 3 Мбайта. Обычно 1 МБ = 2^20 байт, значит 3 МБ = 3 × 2^20 = 3 145 728 байт.
- Найдем B + M
- N × (B + M) = 3 145 728
- 16384 × (B + M) = 3 145 728
- B + M = 3 145 728 / 16 384 = 192.
- Найдем M
- M = (B + M) − B = 192 − 101 = 91.
Ответ: 91.
