Задание №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
Подробнее...
Согласен, что на практике могут использоваться различные приёмы. На мой взгляд, в формулировках заданий должен быть разумный компромисс. Например, я не вижу ничего плохого даже в формулировке "даны A и B, найдите их сумму". Разумеется, кто-то будет искать подвох, не являются ли A и B комплексными или даже матрицами, а если это числа, то в какой системе счисления. Но ведь понятно, что подобные задачи не будут давать школьникам.
Но в данном случае я конечно исправлю формулировку в ближайшее время. Спасибо за конструктивные замечания! Кстати, новые варианты я сейчас публикую на Яндекс.Репетитор, недавно опубликовали еще один.
На практике "не целое количество бит на номер" выражается в том, что двоичным кодом записывается комбинация номеров, а не каждый номер по отдельности.
То есть кодирование не только не посимвольное, но и не пономерное.
Добрый день! Спасибо за замечание про целое количество бит. Конечно, не целое количество бит на практике представить сложно, но теоретически - вполне.
Не указано не только то, что кодирование производится посимвольно, но и то, что каждый номер кодируется целым количеством бит. При хранении 24 номеров единым кодом достаточно 50 байт (в битах - логарифм по основанию 2 от 10 в степени 120).