Тема 11. Количество информации и комбинаторика
11.03 Автомобильные номера
Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела количество информации и комбинаторика
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#7597

Петрович с соседнего подъезда занимается созданием и учётом номеров для машин. Эти номера он отдаёт в местное МВД для людей, которые оформляют свои машины. Каждый созданный номер необходимо внести в общую базу данных, где хранятся номера машин всех россиян. Автомобильный номер состоит из уникальной строки и кода региона. Поступил заказ на всевозможные варианты номеров «АМ*?*АМ» для 250  региона. Нумерация регионов начинается с 1  . Код региона кодируется отдельно от уникальной строки минимально возможным числом бит. Условный знак «?» обозначает все заглавные буквы кириллицы, а «*» обозначет цифры от 0  до 9  включительно. Для кодирования кириллицы в номере используется русский алфавит из 33  букв, который кодируется одинаковым минимально возможным числом бит. Для кодирования любой цифры в номере используется одинаковое минимально возможное число бит. Цифры и буквы в номере кодируются отдельно, а сам номер вместе с кодом региона кодируется минимально возможным количеством байт. Сколько байт информации нужно загрузить Петровичу в базу данных МВД о всех автомобильных номерах по шаблону «АМ*?*АМ» для 250  региона?

Показать ответ и решение

Рассмотрим заказанный номер как "А "М "* "? "* "А "М"
Используется 5  букв из кириллицы и 2  цифры.

От 0  до 9  ровно 10  цифр, поэтому придётся выделить хотя бы 4  бита на кодирование цифры  3              4
2  = 8 < 10 <  2 =  16  .

Один символ кириллицы, состоящий из 33  букв, может быть закодирован не менее, чем 6  битами, так как 25 = 32 < 33 < 26 = 64  .

Итого, (5 ⋅ 6 + 4 ⋅ 2) = 38  бит требуется для кодирования ровно 1  номера без региона с любыми допустимыми значениями на позициях «?»и «*»

Регион 250  может быть закодирован не менее, чем 8  битами, так как от 1  до 256  ровно 256  чисел  7                 8
2 =  128 < 250 < 2  =  256  .

Получаем, что один номер с регионом можно закодированить с помощью 38 + 8 = 46  бит. По условию каждый номер кодируется минимально возможным количеством байт, следовтельно, 6 ⋅ 8 = 48 > 46  можно закодировать номер 6  -ю байтами.

Но в задаче нас просят найти количество информации, которое нужно для кодирования всех возможных вариантов номеров, где вместо «?»может стоять любая буква из кириллицы, а вместо «*»– любая цифра от 0  до 9  .

Комбинаторными вычислениями получаем, что всего возможных вариантов номеров может быть 33 ⋅ 10 ⋅ 10 = 3300

Тогда Петровичу придётся внести

6 ⋅ 3300 = 19800  байт информации о номерах из заказа.

Ответ: 19800

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное обучение
в Школково

Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!