11.03 Автомобильные номера
Ошибка.
Попробуйте повторить позже
Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Автомобильный номер состоит из уникальной строки и кода региона. Поступил заказ на всевозможные варианты номеров «СО*Т?КА» для 128 региона. Нумерация регионов начинается с 1. Код региона кодируется отдельно от уникальной строки минимально возможным числом бит. Условный знак «?» обозначает все буквы кириллицы, а «*» обозначет цифры от 0 до 7 включительно. Для кодирования кириллицы в номере используется русский алфавит из 33 букв, который кодируется одинаковым минимально возможным числом бит. Для кодирования любой цифры в номере используется одинаковое минимально возможное число бит. Цифры и буквы в номере кодируются отдельно, а сам номер вместе с кодом региона кодируется минимально возможным количеством байт.(Количество регионов не превышает 128).
Сколько байт информации нужно загрузить Петровичу в базу данных МВД о всех автомобильных номерах по шаблону «СО*Т?КА» для 128 региона?
Замечание: во всех возможных номерах всегда используется цифра до 0 до 7, не только в
заказе.
Рассмотрим заказанный номер как «С»,«*»,«О»,«Т»,«?»,«К»,«А»Используется 6 букв из кириллицы и 1 цифры.
От 0 до 7 ровно 8 цифр, поэтому придётся выделить 3 бита на кодирование цифры 
.
Один символ кириллицы, состоящий из 33 букв, может быть закодирован не менее, чем 6 битами, так
как 
.
Итого, 
бит требуется для кодирования ровно 1 номера без региона с любыми
допустимыми значениями на позициях «?»и «*»
Регион 128 может быть закодирован не менее, чем 7 битами, так как от 1 до 128 ровно 128 чисел
.
Получаем, что один номер с регионом можно закодированить с помощью 
бит. По
условию каждый номер кодируется минимально возможным количеством байт, следовтельно,
можно закодировать номер 6-ю байтами.
Но в задаче нас просят найти количество информации, которое нужно для кодирования всех возможных вариантов номеров, где вместо «*»может стоят любая буква из кириллицы, а вместо «?»- любая цифра от 0 до 6.
Комбинаторными вычислениями получаем, что всего возможных вариантов номеров может быть
Тогда Петровичу придётся внести
байт информации о номерах из заказа.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
