Разбор всех задач с kompege.ru Ч.26

Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!

№ 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, где:log⁡2(N)=5⇒N>16

2^4=16(4 бита недостаточно)

2^5=32(5 бит достаточно)

Минимальное N: 17 (так как 16 требует 4 бита, а 17 уже требует 5)

6. Проверка для N=17:
Бит на символ: log⁡2(17)=5
Байт на ID: (163×5)/8=102
Общий объем: 32 768 × 102 = 3 342 336 байт (совпадает)

Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov

А также ставьте лайк, пишите комментарии.

ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ

Тут все разборы собраны воедино