Задача к ЕГЭ по информатике на тему «автомобильные номера» №1

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

Рассмотрим заказанный номер как «Г»,«Р»,«6»,«*»,«6»,«О»,«Б»,«?». Используется 5 букв из кириллицы и 3 цифры.

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

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

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

Регион 64 может быть закодирован не менее, чем 6 битами, так как от 1 до 64 ровно 64 числа  6 2  = 64  .

Получаем, что один номер с регионом можно закодированить с помощью 39 + 6 = 45  бит. По условию каждый номер кодируется минимально возможным количеством байт, следовтельно, 6 ⋅ 8 = 48 > 45  » class=»math» src=»/images/inform/reshen/reshen-1113-6.svg» width=»auto»> можно закодировать номер 6-ю байтами. </p>
<p class= Но в задаче нас просят найти количество информации, которое нужно для кодирования всех возможных вариантов номеров, где вместо «*»может стоят любая буква из кириллицы, а вместо «?»- любая цифра от 0 до 6.

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

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

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

Ответ: 1386
Оцените статью
Я решу все!