Задание повышенного уровня сложности, на выполнение отводится 3 минуты. Проверяет умение подсчитывать информационный объем сообщений.
Описание задачи
На предприятии каждой изготовленной детали присваивается серийный номер, содержащий:
- 10 десятичных цифр;
- 52 латинские буквы;
- символы из 960-символьного трехсимвольного специального алфавита.
Для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. Используется посимвольное кодирование, все символы кодируются одинаковым и минимально возможным числом бит.
Известно, что для хранения 2000 серийных номеров отведено не более 693 КБ памяти. Необходимо определить максимально возможную длину серийного номера.
Решение
Обозначим длину серийного номера как k (количество символов).
- Определение размера одного символа:
Общая мощность алфавита: 10 + 52 + 960 = 1022 символа.
Для кодирования 1022 символов требуется минимум 11 бит (2<sup>10</sup> = 1024 < 1022, 2<sup>11</sup> = 2048 > 1022). Таким образом, один символ кодируется 11 битами.
- Определение информационного объема одного номера:
Общий объем памяти: 693 КБ = 693 * 1024 байт = 709632 байта.
Объем памяти на один номер: 709632 байта / 2000 номеров ≈ 354.816 байта. Учитывая ограничение «не более 693 КБ», берем 354 байта на один номер.
- Определение длины серийного номера:
Переводим 354 байта в биты: 354 байта * 8 бит/байт = 2832 бита.
Длина серийного номера: 2832 бита / 11 бит/символ ≈ 257.45 символов.
Округляем результат в меньшую сторону до целого числа, так как длина номера должна быть целым числом.
Заключение
Максимально возможная длина серийного номера составляет 257 символов.