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

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

2016-06-24 15:57:19

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

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

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

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

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

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

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

  1. 140 байт
  2. 210 байт
  3. 280 байт
  4. 420 байт

Решение:

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

2k = N

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

2k ≥ 27


при k = 4:

24 = 16


при k = 5:

25 = 32

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

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

5 ⋅ 6 = 30 бит

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

30 / 8 = 3,75 байт

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

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

4 ⋅ 70 = 280 байт

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

Ответ: 3

До экзаменов еще есть время!

Наверх