Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!
№ 4323 Пробный 06.2022 /dev/inf advanced (Уровень: Сложный)
При регистрации в компьютерной системе каждому объекту присваивается
идентификатор, состоящий из 163 символов. В базе данных для хранения
каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит.
Известно, что для кодирования 32 768 идентификаторов потребовалось
3264 Килобайт. Определите минимальное количество различных символов в
алфавите, который использовали для записи идентификаторов.
В ответе запишите только целое число – количество различных символов.
Аналитически:
1. Дано:
Длина идентификатора: 163 символа
Количество идентификаторов: 32 768
Общий объем: 3 264 КБ = 3 342 336 байт
2. Вычисляем объем на 1 идентификатор:
Байт на ID=3 342 336 / 32 768=102 байт=816 бит
3. Бит на символ:
Бит на символ=816 / 163≈5.006
Так как должно быть целое число бит, пробуем:
5 бит: 2^5=32 символа
6 бит: 2^6=64 символа
4. Проверяем 5 бит:
163×5=815 бит=101 875 байт→102 байт
Общий объем:
32 768×102=3 342 336 байт(ровно влезает)
5. Вычисляем минимальный алфавит:
Нам нужно минимальное N, где:log2(N)=5⇒N>16
2^4=16(4 бита недостаточно)
2^5=32(5 бит достаточно)
Минимальное N: 17 (так как 16 требует 4 бита, а 17 уже требует 5)
6. Проверка для N=17:
Бит на символ: log2(17)=5
Байт на ID: (163×5)/8=102
Общий объем: 32 768 × 102 = 3 342 336 байт (совпадает)
Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov
А также ставьте лайк, пишите комментарии.
ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ
Тут все разборы собраны воедино
