Е11.40 Определите минимально возможную мощность алфавита

На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 261 символов. Для его хранения отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 252 500 серийных номеров отведено не более 31 Мбайт памяти.

Определите минимально возможную мощность алфавита, из которого составляются серийные номера.
В ответе запишите только число.

Ответ:

ЕГЭ по информатике Основная волна 07.06.2024 kompege.ru – задание №11

Решение:

print(31*1024*1024/252500) #128
print(128*8/261) #3.92
print(2**4)

print(261*4/8) #131
print((252500*131)/1024/1024)

print(31*1024*1024/252500) #128

print(128*8/261) #3.92

print(2**4)

print(261*4/8) #131

print((252500*131)/1024/1024)

128.73606336633662
3.9233716475095783
16 (максимум, минимум = 9)

130.5
31.545162200927734

Пошаговое решение

Найдем количество байт, выделенных на один серийный номер:
- Выделенная память: 31 МБ = 31 * 1024 * 1024 байт
- Всего серийных номеров: 252 500
- Байт на один серийный номер:
  
  Python
  
  print(31*1024*1024/252500) # 128.73606336633662 байт
  
  1
  
  print(31*1024*1024/252500) # 128.73606336633662 байт
Переведем количество байт в количество бит и найдем количество бит на один символ:
- Количество бит на один серийный номер: 128.73606336633662 * 8 = 1029.888507930693
- Количество бит на один символ:
  
  Python
  
  print(128*8/261) # 3.9233716475095783 бита
  
  1
  
  print(128*8/261) # 3.9233716475095783 бита
Найдем минимальную мощность алфавита:
- Минимальное количество бит для кодирования символа: 4 (так как 3.92 округляется в большую сторону)
- Максимальная мощность алфавита: 2^4 = 16
Подтвердим расчет:
- Байт на один серийный номер при 4 битах на символ:
  
  Python
  
  print(261*4/8) # 130.5 байт
  
  1
  
  print(261*4/8) # 130.5 байт
- Память для хранения 252 500 серийных номеров:
  
  Python
  
  print((252500*131)/1024/1024) # 31.545162200927734 МБ
  
  1
  
  print((252500*131)/1024/1024) # 31.545162200927734 МБ
- Это значение больше 31 МБ, поэтому расчет верен.

Заключение

Минимально возможная мощность алфавита, из которого составляются серийные номера, составляет 9 (максимально возможная — 16).

Ответ: 9