Подготовка к ЕГЭ и олимпиадам по информатике 2020 / Тренировочные варианты ЕГЭ

Профильная информатика:
подготовка к ЕГЭ и олимпиадам

Вариант № EGE_INF_1701

Добавлен 18 мая 2017 г. в 0:11. Изменён 24 декабря 2017 г. в 22:53.Скачать PDF
1Р 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Задание

В некоторой стране используют автомобильные номера, состоящие из двух частей: ровно двух букв из 10-буквенного алфавита и далее ровно трёх десятичных цифр. Какое минимальное количество байт необходимо зарезервировать для хранения информации о 24 таких номерах?

Решение

Каждый автомобильный номер является последовательностью символов вида \(\alpha_1\alpha_2\beta_1\beta_2\beta_3\), где \(\alpha_i\) - некоторый символ 10-буквенного алфавита и \(\beta_j \in \{0,\dots ,9\} \). Используя правило произведения, определим общее количество возможных автомобильных номеров \(N=10^2\cdot 10^3 = 10^5\).

Минимальное количество бит для кодирования \(N\) комбинаций определяется по формуле \(i = \left\lfloor \log_{2}N \right\rfloor \), где операция \(\left\lfloor\,\right\rfloor \) обозначает округление вверх до ближайшего целого. Потенцируя обе части, получим \(2^i \ge 10^5\), что справедливо при \(i=17\): \[ 2^{17} = 2^{7+10} = 128 \cdot 1024 > 128\cdot1000 > 10^5. \]

Таким образом, на один автомобильный номер будет затрачено 17 бит. Соответственно, на 24 автомобильных номера будет затрачено \( \frac{17 \cdot 24}{8} = 51 \) байт.

Подробнее...

Замечание

В условии задачи явно не указано, что кодирование должно производиться посимвольно. В случае посимвольного кодирования увеличивается избыточность кода: на кодирование каждой буквы или цифры требуется 4 бита, но при этом используется только 10 кодовых слов из 16 возможных. Одинаковый ответ с рассмотренным выше решением гарантирован лишь в случае, когда мощность первичного алфавита является натуральной степенью числа 2.

Подробнее...

Ответ

51

Подробнее...