Подтема 5 из 6
Составной код
Код из частей со своими алфавитами и номер, записанный двоичным числом: где выделяют целые байты.
Части кода
Идентификатор — 4 заглавные латинские буквы и 3 цифры. Сколько байт он занимает, если у каждой части свой код символа?
У каждой части свой алфавит и своё число битов на символ; биты частей складывают. Буквы: 26 → 5 бит, 4 · 5 = 20 бит. Цифры: 10 → 4 бита, 3 · 4 = 12 бит. Вместе 32 бита = 4 байта.
Если же «все символы кодируются одинаковым числом бит», алфавит общий: 26 + 10 = 36, по 6 бит, 7 · 6 = 42 бита → 6 байт. Решает формулировка условия.
Номер числом
К паролю задачи темы добавили номер отдела от 1 до 500, записанный двоичным числом минимальной длины. Сколько бит занимает номер?
Число от 1 до m в двоичной записи занимает j бит, где 2ʲ > m: j битов записывают числа только до 2ʲ − 1. 2⁸ = 256 ≤ 500 < 512 = 2⁹, номеру нужно 9 бит.
Это не то же, что код варианта. 128 разным объектам хватит 7 бит — коды от 0000000 до 1111111. А само число 128 = 10000000 — восемь цифр.
«Номер записан как двоичное число» — ищи степень двойки, строго бо́льшую наибольшего номера. «Тип — одно из N значений, кодируется минимальным числом бит» — это N вариантов, как алфавит: 2ʲ ≥ N. Ответы различаются, только когда m — степень двойки.
Метод — число цифр двоичной записи числа. Скобки вокруг числа нужны, чтобы точку не приняли за дробную часть:
print((500).bit_length(), (128).bit_length(), bits(128))Где выделяют байты
Пароль (90 бит) и номер отдела (9 бит) хранят вместе. Сколько байт они занимают?
Ответ зависит от того, чему условие выделяет целые байты: всему коду — сложи биты и округли; каждой части — округли каждую. Подряд: 90 + 9 = 99 бит → 13 байт. Отдельно: 12 + 2 = 14 байт.
Если в той же базе 40 записей заняли 1200 байт, запись — 30 байт, и сведениям остаётся 30 − 13 = 17 байт, когда пароль и номер записаны подряд, или 30 − 14 = 16 байт, когда у каждого свои байты.
from math import ceilpassword = 15 * bits(62)number = (500).bit_length()together = ceil((password + number) / 8)apart = ceil(password / 8) + ceil(number / 8)print(together, apart, 30 - together, 30 - apart)Тонкости:объект из блоков
Объект описывают блоками: блок — тип (одно из 9 значений, 4 бита) и три буквы (3 · 5 = 15 бит), всего 19 бит. Десять блоков подряд — 190 бит → 24 байта; если целые байты у каждого блока — 10 · 3 = 30 байт. Считают снизу вверх: элемент, блок, объект, все объекты. Если место резервируют под наибольшее число блоков, считают по нему.
Итого
- Частиу каждой свой алфавит, биты складывают
- Общий код«все символы одинаково» — один алфавит
- Номер числом2ʲ > m,
m.bit_length() - Варианты2ʲ ≥ N, как у алфавита
- Байты всемусложить биты, потом округлить
- Байты частямокруглить каждую часть
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Байты всему коду
Код состоит из пяти заглавных латинских букв и трёх десятичных цифр. У каждой части своё минимальное число битов на символ, целые байты выделяются всему коду. Сколько байтов займёт код?
Введите число.
Подсказка
Целые байты всему коду: сложи биты частей, потом округляй.
Решение
Буквы: 5 · 5 = 25 бит, цифры: 3 · 4 = 12 бит. Целые байты всему коду — складываем биты: 37 бит → 5 байтов. С отдельными байтами у частей вышло бы 4 + 2 = 6.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i a, d = 5 * bits(26), 3 * bits(10)print(ceil((a + d) / 8))Ответ: 5
Общий код для букв и цифр
Код состоит из 6 заглавных латинских букв и 4 цифр от 1 до 9 (ноль не используется). Все 10 символов кодируются одним общим кодом одинаковой минимальной длины, код занимает минимальное целое число байтов. Сколько байтов займёт код?
Введите число.
Подсказка
Один общий код — один алфавит на все символы.
Решение
Цифр без нуля девять, общий алфавит 26 + 9 = 35, на символ 6 бит. Код 10 · 6 = 60 бит → 8 байтов. Если бы у частей были свои коды, вышло бы 6 · 5 + 4 · 4 = 46 бит → 6 байтов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print(ceil(10 * bits(26 + 9) / 8))Ответ: 8
Номер 256 двоичным числом
Сколько битов нужно, чтобы записать двоичным числом номер от 1 до 256?
Введите число.
Подсказка
Число от 1 до m записывают j битами, если 2ʲ > m.
Решение
Восемью битами записываются числа только до 255, а 256 = 100000000 — девять цифр. Для 256 разных объектов хватило бы 8 бит, но здесь нужно записать само число.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i print((256).bit_length())Ответ: 9
Срок действия на пропуске
На пропуске записаны личный код из 10 заглавных латинских букв (минимальное целое число байтов) и срок действия: номер года от 0 до 63 и номер дня от 1 до 366, оба двоичными числами минимальной длины, а вместе — минимальное целое число байтов. Сколько байтов занимает вся информация на пропуске?
Введите число.
Подсказка
Год и день — двоичные числа минимальной длины, вместе в целых байтах.
Решение
Код 10 · 5 = 50 бит → 7 байтов. Год до 63 — 6 бит, день до 366 — 9 бит, вместе 15 бит → 2 байта. Всего 7 + 2 = 9 байтов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i code = ceil(10 * bits(26) / 8)term = ceil(((63).bit_length() + (366).bit_length()) / 8)print(code + term)Ответ: 9
Дополнительные данные объекта
Код объекта состоит из двух частей: категория — 8 заглавных латинских букв, номер внутри категории — целое число от 1 до 5000, записанное как двоичное число минимальной длины. Буквы кодируются посимвольно минимальным числом битов, код в целом занимает минимальное целое число байтов. Кроме кода, для каждого объекта выделено одинаковое целое число байтов дополнительных данных. Для 64 объектов потребовалось 2368 байтов. Сколько байтов дополнительных данных приходится на объект?
Введите число.
Подсказка
Код — буквы категории и номер вместе, в общих целых байтах.
Решение
Категория 8 · 5 = 40 бит, номер до 5000 — 13 бит, вместе 53 бита → 7 байтов. Запись 2368 / 64 = 37 байтов, дополнительные данные 37 − 7 = 30.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i code = ceil((8 * bits(26) + (5000).bit_length()) / 8)print(2368 // 64 - code)Ответ: 30
Номер в своих байтах
Личный код сотрудника — 13 символов, каждый из которых одна из 12 разрешённых букв или одна из 10 цифр; код кодируется посимвольно одинаковым минимальным числом битов и занимает минимальное целое число байтов. Номер подразделения — целое число от 1 до 100, записан двоичным числом и занимает минимальное целое число байтов. Всего на пропуске 32 байта данных. Сколько байтов выделено дополнительным сведениям?
Введите число.
Подсказка
У кода и номера свои целые байты.
Решение
Алфавит кода — 12 букв и 10 цифр, N = 22, на символ 5 бит: 13 · 5 = 65 бит → 9 байтов. Номер до 100 двоичным числом — 7 бит → свой 1 байт. Сведения: 32 − 9 − 1 = 22 байта.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i code = ceil(13 * bits(22) / 8)number = ceil((100).bit_length() / 8)print(32 - code - number)Ответ: 22
Номер вместе с кодом
То же, что в задаче 4, но личный код и номер подразделения записаны подряд и вместе занимают минимальное целое число байтов. Сколько байтов выделено дополнительным сведениям?
Введите число.
Подсказка
Код и номер вместе: сложи биты, потом округляй.
Решение
Код 65 бит и номер 7 бит записаны подряд: 72 бита = ровно 9 байтов. Сведения: 32 − 9 = 23 байта.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i both = ceil((13 * bits(22) + (100).bit_length()) / 8)print(32 - both)Ответ: 23
Описания 4096 объектов
Объект описывается 30 блоками (место отведено под 30 блоков у каждого объекта). Блок — код из 5 символов, каждый из которых заглавная латинская буква или цифра, и тип — одно из чисел от 1 до 1000, кодируется минимальным числом битов; блок в целом занимает минимальное целое число байтов. Сколько Кбайт займут описания 4096 объектов?
Введите число.
Подсказка
Считай снизу вверх: блок, объект, все объекты.
Решение
Буквы и цифры — 36 символов, по 6 бит: 5 · 6 = 30 бит; тип — одно из 1000 значений, 10 бит. Блок 40 бит = 5 байтов, объект 30 · 5 = 150 байтов, 4096 объектов — 614 400 байтов = 600 Кбайт.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i block = ceil((5 * bits(36) + (1000).bit_length()) / 8)print(4096 * 30 * block // 1024)Ответ: 600
Дополнительная информация объекта
Описание объекта включает идентификатор из 6 заглавных латинских букв (каждая кодируется минимальным числом битов, идентификатору — минимальное целое число байтов), структуру и дополнительную информацию. Структура — последовательность простых элементов, всего 3000 видов; каждый элемент кодируется одинаковым минимальным числом битов, под структуру выделено минимальное целое число байтов, достаточное для 40 элементов. Для дополнительной информации выделено одинаковое целое число байтов. Данные о 16 384 объектах заняли 2 Мбайт. Сколько байтов дополнительной информации приходится на объект?
Введите число.
Подсказка
Из записи вычти идентификатор и структуру.
Решение
Идентификатор 6 · 5 = 30 бит → 4 байта. Элементам 3000 видов нужно 12 бит, структура 40 · 12 = 480 бит = 60 байтов. Запись 2 · 2²⁰ / 16 384 = 128 байтов, дополнительная информация 128 − 4 − 60 = 64.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i ident = ceil(6 * bits(26) / 8)struct = ceil(40 * bits(3000) / 8)print(2 * 2 ** 20 // 16_384 - ident - struct)Ответ: 64