На предприятии каждой изготовленной детали присваивается серийный номер, состоящий из 248 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 75 600 серийных номеров требуется более 16 Мбайт памяти.
Определите минимально возможную мощность алфавита, используемого для записи серийных номеров. В ответе запишите только целое число.
Алгоритм решения задания 11. Часть 3
Тип 3. Мощность алфавита
В предыдущей статье мы находили объём памяти по известной мощности алфавита. Теперь решим обратную задачу: по длине записи, количеству объектов и ограничению памяти восстановим мощность алфавита.
В условии могут попросить минимальную или максимальную мощность. Поэтому важно не только найти число бит на символ, но и правильно выбрать границу диапазона.
Мощность алфавита
Обозначим через L длину одной записи, через K количество записей, а через M общий объём памяти. Число бит на символ обозначим i, мощность алфавита — N.
Если на символ выделено i бит, можно закодировать не более 2ⁱ разных символов. Это максимальная мощность алфавита для выбранного числа бит.
Минимальная мощность, для которой уже потребуется i бит, равна 2ⁱ⁻¹ + 1. Предыдущее число, 2ⁱ⁻¹, ещё можно было бы закодировать с помощью i − 1 бит.
Размер одной записи находим так: умножаем L на i и делим результат на 8. Если получилось дробное число байт, округляем его вверх, потому что запись занимает целое число байт.
Алгоритм решения
Решать третий тип можно тремя способами: вручную по формулам, по тем же формулам в Python или перебором возможного числа бит.
Независимо от способа придерживаемся одной последовательности действий:
- Выписываем длину записи L, количество объектов K и ограничение памяти M.
- Переводим память в байты: Кбайты умножаем на 2¹⁰, Мбайты — на 2²⁰, Гбайты — на 2³⁰.
- Определяем, сколько бит может или должно приходиться на один символ. Размер каждой записи округляем вверх до целого числа байт.
- Строго повторяем знак из условия: «не более» означает ≤, «более» — >, «не менее» — ≥.
- Для максимальной мощности берём 2ⁱ. Для минимальной мощности, которой уже нужны i бит, берём 2ⁱ⁻¹ + 1.
Пример 1. Ручное решение
Начнём с задачи на минимальную мощность алфавита.
Сначала переводим память в байты: 16 · 2²⁰ = 16 777 216 байт.
Разделим общий объём на количество номеров: 16 777 216 / 75 600 ≈ 221,92 байта.
В условии сказано «более 16 Мбайт». Если выделить 221 байт на номер, порог не будет превышен. Поэтому одной записи должно соответствовать как минимум 222 байта.
Теперь проверим число бит на символ. При i = 7 один номер занимает 248 · 7 = 1736 бит, или 217 байт. Этого недостаточно.
При i = 8 получаем 248 · 8 = 1984 бита, или 248 байт. Общий объём становится больше 16 Мбайт, поэтому подходят восемь бит на символ.
Семь бит позволяют закодировать 2⁷ = 128 символов. Следовательно, минимальная мощность, для которой уже потребуются восемь бит, равна 128 + 1 = 129. Ответ: 129.
Пример 2. Решение по формулам в Python
Теперь решим задачу на максимальную мощность. Перебирать значения пока не будем: последовательно запишем в Python те же формулы, которые использовали бы при ручном решении.
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 246 символов. В базе данных для хранения каждого серийного номера отведено одинаковое и минимально возможное число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным числом бит. Известно, что для хранения 703 569 серийных номеров доступно не более 77 Мбайт памяти.
Определите максимально возможную мощность алфавита, используемого для записи серийных номеров.
В ответе запишите только целое число.
Переводим память в байты. Затем целочисленным делением находим, сколько полных байт можно выделить одной записи, не превысив общий лимит.
length = 246
objects = 703_569
memory = 77 * 2 ** 20
bytes_per_object = memory // objectsОператор целочисленного деления // отбрасывает дробную часть. Это соответствует словам «не более»: лишний байт на каждую запись уже может привести к превышению лимита. Можно было воспользоваться и функцией floor из math, но проще пойти через деление.
Теперь переводим допустимый размер записи в биты и делим на её длину. Снова берём только целую часть, потому что ищем максимальное целое число бит на один символ.
bits = bytes_per_object * 8 // lengthЕсли на символ выделено bits бит, максимальная мощность алфавита равна 2 в степени bits.
alphabet = 2 ** bits
print(alphabet)Полная программа выглядит так:
length = 246
objects = 703_569
memory = 77 * 2 ** 20
bytes_per_object = memory // objects
bits = bytes_per_object * 8 // length
alphabet = 2 ** bits
print(alphabet)Python получает 114 байт на одну запись и 3 бита на символ. Следовательно, максимальная мощность равна 2³ = 8. Ответ: 8.
Пример 3. Решение перебором
Перебор удобен, когда из-за округления до целого числа байт формулы становятся громоздкими. Мы проверяем небольшие значения i и каждый раз полностью повторяем условие задачи.
На предприятии каждой изготовленной детали присваивают серийный номер, состоящий из 2783 символов. В базе данных каждый серийный номер занимает одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование серийных номеров, все символы кодируются одинаковым и минимально возможным целым числом бит.
Известно, что для хранения 3 845 627 серийных номеров требуется не менее 11 Гбайт памяти.
Определите минимально возможную мощность алфавита, используемого для записи серийных номеров.
В ответе запишите только целое число.
Запишем исходные данные и переведём 11 Гбайт в байты, не забывая про импорт функции ceil:
from math import ceil
length = 2783
objects = 3_845_627
memory = 11 * 2 ** 30Перебираем число бит от меньшего к большему. Для каждого значения определяем размер одной записи и общий объём всей базы.
for bits in range(1, 33):
bytes_per_object = ceil(length * bits / 8)
total_memory = objects * bytes_per_objectФункция ceil округляет размер записи вверх. Это обязательно: даже небольшая дробная часть потребует ещё одного целого байта.
Ищем первое значение, при котором общий объём станет не меньше 11 Гбайт. Знак ≥ точно повторяет условие задачи.
if total_memory >= memory:
alphabet = 2 ** (bits - 1) + 1
print(alphabet)
breakКоманда break завершает цикл после первого подходящего значения. Это важно: нам нужна минимальная мощность, а все следующие значения bits дадут ещё больший алфавит.
Полный код решения:
from math import ceil
length = 2783
objects = 3_845_627
memory = 11 * 2 ** 30
for bits in range(1, 33):
bytes_per_object = ceil(length * bits / 8)
total_memory = objects * bytes_per_object
if total_memory >= memory:
alphabet = 2 ** (bits - 1) + 1
print(alphabet)
breakПри восьми битах общий объём ещё меньше 11 Гбайт. Первым подходит i = 9, поэтому минимальная мощность равна 2⁸ + 1 = 257. Ответ: 257.
Итоги
В третьем типе задания 11 мы восстанавливаем мощность алфавита по ограничению памяти. Сначала определяем число бит на символ, а затем выбираем нужную границу диапазона.
Для максимальной мощности используем 2ⁱ. Для минимальной мощности, которой уже требуется i бит, используем 2ⁱ⁻¹ + 1.
Всегда следите за словами «не более», «более» и «не менее». Проверяйте знак сравнения и округляйте размер каждой записи вверх до целого числа байт.
Шаблон решения перебором
Ниже приведён шаблон того же перебора, который мы использовали в примере 3. В нём меняются только исходные данные, знак сравнения и формула для ответа.
from math import ceil
length = *1
objects = *2
memory = *3
for bits in range(1, 33):
bytes_per_object = ceil(length * bits / 8)
total_memory = objects * bytes_per_object
if total_memory *4 memory:
alphabet = *5
print(alphabet)
breakПодставляем значения по пунктам:
*1— длина одной записи в символах;*2— количество записей;*3— ограничение памяти, заранее переведённое в байты;*4— знак сравнения из условия, например >= для слов «не менее»;*5— формула для искомой мощности алфавита. Если нужно найти минимальную мощность, которой уже требуетсяbitsбит, записываем2 ** (bits - 1) + 1.
Шаблон повторяет решение выше строка в строку. Цикл проверяет значения bits от меньшего к большему, а break останавливает перебор на первом подходящем значении.
Поэтому такой вариант удобно использовать, когда требуется минимальная мощность алфавита. Если в задаче ищется максимальная мощность, проще применить формульный способ из предыдущего раздела.
На этом мы закончили разбор всех типов задания 11 ЕГЭ по информатике. Попрактиковаться в решении можно в нашем тренажёре.
