Подтема 6 из 6 · дополнительный урок
Служебные данные, зависящие от размера
Сообщение группами с заголовками и номер, длина которого зависит от числа изделий.
Группы с заголовками
Дополнительный урок — для продвинутых: такие задачи редки и на экзаменах пока не встречались.
Сообщение в 10 байт делят на группы не больше 4 байт, к каждой группе добавляют заголовок в 1 байт. Сколько байт передают?
Заголовков столько, сколько групп, и неполная последняя группа тоже получает заголовок. Группы 4, 4 и 2 байта — три заголовка, всего 10 + 3 = 13 байт. Число групп — деление с округлением вверх: 10 / 4 = 2,5 → 3.
Обратный вопрос: алфавит — 40 символов (6 бит), сообщение в целых байтах, с заголовками не больше 20 байт. Какое наибольшее число символов в сообщении? Объём сообщения перебирают, пока с заголовками он помещается: 16 байт + 4 заголовка = 20, а 17 + 5 = 22 — уже нет. 16 байт — 128 бит, 128 / 6 = 21,3 → 21 символ.
from math import ceilsize = 0while (size + 1) + ceil((size + 1) / 4) <= 20: size += 1print(size, 8 * size // bits(40))Номер зависит от количества
В партии n изделий. Запись изделия — код партии из 5 заглавных латинских букв, номер изделия от 1 до n двоичным числом и 10 байт сведений; код и номер вместе занимают целые байты. Сколько изделий поместится в 1 Кбайт?
Когда длина номера зависит от числа изделий, размер записи меняется вместе с n — его считают заново для каждого n. Код партии — 25 бит. До 63 изделий номеру хватает 6 бит, с 64 — нужно 7, со 128 — 8.
Удобнее всего перебор количества (): для каждого n — запись и общий объём. Перебор можно ограничить: одни сведения занимают 10 байт, больше 1024 // 10 изделий не поместится.
from math import ceilbest = 0for n in range(1, 1024 // 10 + 1): code = ceil((25 + n.bit_length()) / 8) if n * (code + 10) <= 1024: best = nprint(best)Проверка: 73 изделия — номер 7 бит, код 25 + 7 = 32 бита = 4 байта, 73 · 14 = 1022 байта; 74 изделия — 74 · 14 = 1036, уже больше 1024.
Итого
- Группыразмер / группа, вверх
- Заголовкипо одному на каждую группу
- Номер от nn.bit_length() меняется с n
- Перебордля каждого n — запись и объём
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
limit // 10?ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Сообщение с заголовками
Сообщение занимает 25 байтов. Его делят на группы не более чем по 6 байтов, к каждой группе добавляют заголовок в 2 байта. Сколько байтов передаётся вместе с заголовками?
Введите число.
Подсказка
Неполная последняя группа тоже получает заголовок.
Решение
Групп 25 / 6 = 4,17 → 5: четыре по 6 байтов и одна неполная в 1 байт. Заголовков тоже пять: 25 + 5 · 2 = 35 байтов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(25 + ceil(25 / 6) * 2)Ответ: 35
Наибольшее число символов
Алфавит сообщения содержит 100 символов, символы кодируются посимвольно одинаковым минимальным числом битов, сообщение в целом — минимальным целым числом байтов. Сообщение делят на группы не более чем по 5 байтов и к каждой добавляют заголовок в 1 байт. Объём с заголовками — не более 60 байтов. Какое наибольшее число символов может быть в сообщении?
Введите число.
Подсказка
Сначала наибольший объём сообщения вместе с заголовками.
Решение
Сообщение в 50 байтов — 10 групп, 50 + 10 = 60; в 51 байт — уже 11 групп, 62. Значит, сообщение не больше 50 байтов = 400 бит. 100 символам нужно 7 бит, 400 / 7 = 57,1 → 57 символов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i size = max(b for b in range(1, 100) if b + ceil(b / 5) <= 60)print(size * 8 // bits(100))Ответ: 57
Сообщение не более 2 Кбайт
Для передачи сообщений используется алфавит из 300 символов, кодирование посимвольное, каждый символ кодируется одинаковым минимальным числом битов, сообщение в целом — минимальным числом байтов. При передаче сообщение делится на группы не более чем по 7 байтов, к каждой добавляется заголовок из 1 байта. Суммарный размер при передаче — не более 2 Кбайт. Какое наибольшее количество символов может входить в сообщение?
Введите число.
Подсказка
Сначала наибольший объём сообщения, затем символы.
Решение
Сообщение в 1792 байта — 256 групп по 7, 1792 + 256 = 2048; на байт больше — уже 257 групп и 2050. 300 символам нужно 9 бит, 1792 · 8 / 9 = 1592,9 → 1592 символа.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i size = max(b for b in range(1, 3000) if b + ceil(b / 7) <= 2048)print(size * 8 // bits(300))Ответ: 1592
Код изделия больше 4 байтов
Код изделия — код партии из 4 заглавных латинских букв и номер изделия от 1 до n, записанный двоичным числом минимальной длины; код изделия в целом занимает минимальное целое число байтов. При каком наименьшем числе изделий в партии код изделия займёт больше 4 байтов?
Введите число.
Подсказка
Длина номера растёт вместе с числом изделий.
Решение
Код партии 4 · 5 = 20 бит. Больше 4 байтов — больше 32 бит, то есть номеру нужно хотя бы 13 бит. 13 битов нужны числу начиная с 2¹² = 4096.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(min(n for n in range(1, 100_000) if 4 * bits(26) + n.bit_length() > 32))Ответ: 4096
Изделий в партии не более 8 Кбайт
Код партии — 10 заглавных латинских букв; номер изделия от 1 до n записан двоичным числом, одинаковой для всех номеров минимальной длины; код партии и номер вместе занимают минимальное целое число байтов; дополнительные данные — 20 байтов на изделие. Для всей партии используется не более 8 Кбайт. Какое наибольшее число изделий может быть в партии?
Введите число.
Подсказка
Длина номера зависит от числа изделий — перебирай n.
Решение
Перебор числа изделий: для n от 256 до 511 номер — 9 бит, код 50 + 9 = 59 бит → 8 байтов, запись 28 байтов. 292 · 28 = 8176 ≤ 8192, а 293 · 28 = 8204 — уже больше.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i best = 0for n in range(1, 2000): record = ceil((10 * bits(26) + n.bit_length()) / 8) + 20 if n * record <= 8 * 1024: best = nprint(best)Ответ: 292
Изделий в партии не более 60 Кбайт
Каждая партия получает код из 15 символов, каждый — строчная или заглавная латинская буква, символы кодируются одинаковым минимальным числом битов. Изделия получают номера от 1 до числа изделий в партии; номер записывается как двоичное целое число одинаковой для всех номеров минимальной длины. Код партии и номер вместе занимают минимальное целое число байтов, дополнительная информация — 45 байтов на изделие. Для информации обо всех изделиях партии используется не более 60 Кбайт. Какое наибольшее количество изделий может быть в партии?
Введите число.
Подсказка
Перебирай число изделий: длина номера зависит от него.
Решение
52 буквам нужно 6 бит, код партии 15 · 6 = 90 бит. Перебор числа изделий: при n до 2047 номер — 11 бит, код 101 бит → 13 байтов, запись 58 байтов. 1059 · 58 = 61 422 ≤ 61 440, а 1060 · 58 = 61 480 — больше.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i best = 0for n in range(1, 3000): record = ceil((15 * bits(52) + n.bit_length()) / 8) + 45 if n * record <= 60 * 1024: best = nprint(best)Ответ: 1059