В некоторой стране автомобильный номер составляют из заглавных букв

2016-06-24 15:57:19

Формулировка задания: В некоторой стране автомобильный номер длиной K символов составляют из заглавных букв (используется M различных букв) и любых десятичных цифр. Буквы с цифрами могут следовать в любом порядке. Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит). Определите объём памяти, отводимый этой программой для записи N номеров.

Задание входит в ЕГЭ по информатике для 11 класса под номером 13 (Вычисление количества информации).

Рассмотрим, как решаются подобные задания на примере.

Пример задания:

В некоторой стране автомобильный номер длиной 6 символов составляют из заглавных букв (используется 17 различных букв) и любых десятичных цифр. Буквы с цифрами могут следовать в любом порядке.

Каждый такой номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт (при этом используют посимвольное кодирование и все символы кодируются одинаковым и минимально возможным количеством бит).

Определите объём памяти, отводимый этой программой для записи 70 номеров.

140 байт
210 байт
280 байт
420 байт

Решение:

Воспользуемся формулой определения количества информации для вычисления числа бит, требуемых для кодирования одного символа автомобильного номера:

2^k = N

где k – информационный вес символа в битах, а N – количество информации. Нужно подобрать такое минимальное k, чтобы можно было закодировать каждый символ из 27 (17 букв и 10 цифр). То есть:

2^k ≥ 27

при k = 4:

2⁴ = 16

при k = 5:

2⁵ = 32

4 бит не хватит для кодирования 27 символов, а 5 как раз достаточно.

Теперь вычислим, сколько бит будет занимать автомобильный номер длиной 6 символов, если один символ кодируется 5 битами:

5 ⋅ 6 = 30 бит

По условию задачи каждый номер в компьютерной программе записывается минимально возможным и одинаковым целым количеством байт. Поэтому переведем биты в байты:

30 / 8 = 3,75 байт

Округляем результат в большую сторону и получаем, что для хранения в памяти одного автомобильного номера требуется 4 байта.

Осталось вычислить объём памяти, отводимый программой для записи 70 номеров:

4 ⋅ 70 = 280 байт

Это ответ номер 3.

Ответ: 3

ЕГЭ все задания ЕГЭ задание 13

Поделитесь статьей с одноклассниками «В некоторой стране автомобильный номер составляют из заглавных букв – как решать».

При копировании материалов с сайта ссылка на источник обязательна. Уважайте труд людей, которые вам помогают.
Нашли ошибку? Выделите текст и нажмите Ctrl + Enter.