DVBogdanov.ru / Тренировочный вариант по информатике, задание 13

Задание №1701/13

Задание

В некоторой стране используют автомобильные номера, состоящие из двух частей: ровно двух букв из 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

Подробнее...
Добавить комментарий
Комментарии (0)
#Алфавитный подход #Задачи на кодирование информации #Кодирование текста #Определение количества информации #Подготовка к ЕГЭ по информатике #Равномерное кодирование