Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!
№ 463 Джобс 12.10.2020 (Уровень: Сложный)
Автомобильный номер состоит из одиннадцати букв русского алфавита
A, B,C, E, H, K, M, O, P, T, X и десятичных цифр от 0 до 9. Каждый номер состоит из двух букв, затем идет 3 цифры и еще одна буква. Например, АВ901С.
В системе каждый такой номер кодируется посимвольно, при этом каждая буква и каждая цифра кодируются одинаковым минимально возможным количеством бит.
Укажите, сколько бит на один номер можно сэкономить, если кодировать с помощью одинакового минимально возможного количества бит каждую из трех групп – первые две буквы, три цифры и последняя буква.
Аналитически:
1. Определим мощность алфавита и биты на символ
- Буквы: 11 возможных (A, B, C, E, H, K, M, O, P, T, X)
Бит на букву: ⌈log₂11⌉ = 4 бита (так как 2³ = 8 < 11 ≤ 16 = 2⁴) - Цифры: 10 возможных (0-9)
Бит на цифру: ⌈log₂10⌉ = 4 бита (так как 2³ = 8 < 10 ≤ 16 = 2⁴)
2. Текущий способ кодирования (посимвольный)
Номер имеет структуру: 2 буквы + 3 цифры + 1 буква
- Бит на номер:
2×4 (буквы)+3×4 (цифры)+1×4 (буква)=8+12+4=24 бита
3. Новый способ кодирования (группами)
Разобьём номер на 3 группы:
- Первые 2 буквы (11 × 11 = 121 комбинация)
Бит на группу: log₂121 = 7 бит (так как 2⁷ = 128 ≥ 121) - 3 цифры (10 × 10 × 10 = 1000 комбинаций)
Бит на группу: log₂1000 = 10 бит (так как 2¹⁰ = 1024 ≥ 1000) - Последняя буква (11 комбинаций)
Бит на группу: log₂11 = 4 бита
- Бит на номер (новый способ):
7 (2 буквы)+10 (3 цифры)+4 (буква)=21 бит
4. Экономия бит
24 бит (старый способ)−21 бит (новый способ)=3 бита
Если вам понравился разбор - можете поддержать автора с помощью функции "доната". Спасибо
Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov
А также ставьте лайк, пишите комментарии.
ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ
Тут все разборы собраны воедино