Задание 11

Пример 1

При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 404 символов и содержащий только десятичные цифры и символы из 300-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.

Определите объём памяти (в Кбайт), необходимый для хранения 3072 идентификаторов. В ответе запишите только целое число — количество Кбайт.

Теория

Необходимо знать принципы кодирования текстовой информации и помнить степени числа 2, хотя бы до 2¹²=4096, а также уметь переводить биты в байты, байты в килобайты и мегабайты, а также наоборот.

1 байт = 8 (2³) бит
1 Кбайт = 1024 (2¹⁰) байт = 2¹³ бит
1 Мбайт = 1024 (2¹⁰) Кбайт = 2²⁰ байт = 2²³ бит
1 Гбайт = 1024 (2¹⁰) Мбайт = 2²⁰ Кбайт = 2³⁰ байт =2³³ бит
1 Пбайт = 1024 (2¹⁰) Гбайт = 2²⁰ Мбайт = 2³⁰ Кбайт = 2⁴⁰ байт = 2⁴³ бит
1 Эбайт = 1024 (2¹⁰) Пбайт = 2²⁰ Гбайт = 2³⁰ Мбайт = 2⁴⁰ Кбайт = 2⁵⁰ байт = 2⁵³ бит

Кодирование текстовой информации заключается в определении мощности алфавита (множества всех символов) и определение минимального числа бит - i (сколько бит позволяют закодировать алфавит из целого количества символов N, для этого решаем уравнение аналогичное уравнению при кодировании графической информации
и находим i - должно быть целое число и 2ⁱ ≥ N, а 2^i-1 < N. Например N = 80, тогда 2⁶ < 80 ≤ 2⁷ и i = 7 (для кодирования алфавита из 80 символов понадобится 7 бит). Далее умножаем число i на количество символов в идентификаторе или пароле и получаем необходимое количество бит для хранения текста. В задачах для хранения обычно отводится целое количество байт, поэтому полученное число разделите на 8 и результат округлите до ближайшего большего целого.

Решение

Пример 1

В данной задаче мощность алфавита (множество всех символов) равно 300 + 10 = 310. 2⁸ < 310 ≤ 2⁹. Получаем, что для кодирования 1 символа идентификатора необходимо 9 бит. Следовательно для кодирования всего идентификатора вычисляем 404 * 9 / 8 = 454,5 и округляем до большего целого = 455 байт (по условию задачи для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт). Осталось вычислить 455 * 3072 / 1024 = 1365 Килобайт.  

Ответ

1365 (Время не более 2 минут)