Задание 11 · Информационный объём сообщения
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — сколько байт выделено на сведения, если 40 записей «пароль из 15 символов + сведения» занимают 1200 байт, — прошла через подтемы, и каждая добавляла к ней новый вопрос. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Пароль в байтах»: алфавит, биты и байты пароля. Точками отмечены новые строки.
- Подтема 2, «Дополнительные сведения»: запись — пароль и сведения.
- Подтема 3, ««Не более»»: наибольшее — округлить вниз.
- Подтема 4, ««Более» и «не менее»»: наименьшее — следующее целое.
- Подтема 5, «Составной код»: части подряд или по отдельности. Ответ задачи темы — 18 байт.
Числа остаются теми же — меняется вопрос: размер части, наибольшее или наименьшее значение, составной код. Дополнительный урок добавляет служебные данные, которые зависят от размера.
Карта темы
Каждая подтема дала одно правило, и любое решение собирается из них. Сверху — путь от алфавита к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- АлфавитN разных символов: наборы складывают
- Битынаименьшее i, при котором 2ⁱ ≥ N
- Байтывверх — тому, чему их выделяют
1Пароль в байтах
- K · i битдлина пароля × биты символа
- байты пароляK · i / 8 с округлением вверх
- все паролисначала байты одного, потом × число
2Дополнительные сведения
- записьпамять / число записей
- сведениязапись минус пароль
- части в битахесли байты на всю запись — сложить, потом вверх
3Наибольшее значение: «не более»
- длинанаибольшее K: K · i ≤ биты
- алфавитнаибольший при i битах — 2ⁱ
- число записейпамять // запись, вниз
4Наименьшее значение: «более» и «не менее»
- не помещается в n байтK · i > 8n
- алфавитнаименьший для i битов — 2ⁱ⁻¹ + 1
- «более»ровно граница не подходит
5Составной код
- число до mj бит, где 2ʲ > m
- подрядсложить биты частей, потом вверх
- по частямкаждую часть вверх, потом сложить
6Служебные данные, зависящие от размерадополнительный урок
- группызаголовок на каждую группу, число групп вверх
- номер от nперебрать количество
Как решать
Любое задание 11 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Перед расчётом ответь на три вопроса:
- Что спрашивают: объём, сведения, длину, алфавит или число записей?
- Чему выделяют целые байты: символу, паролю, записи или всему коду?
- Граница «не более», «более» или «не менее» — какого соседа проверить?
Частые ошибки
Восемь ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- 26 · 10
- наборы символов перемножили → складывают: 10 + 26 + 26 = 62. Спроси себя: сколько разных символов можно поставить?подтема 1
- 11,25 → 11
- 90 бит — 11 байт → только вверх: 12 байт. Спроси себя: поместятся ли 90 бит в 88?подтема 1
- все вместе
- 40 · 90 / 8 = 450 байт → 12 байт на пароль · 40 = 480. Спроси себя: кому выделяют целые байты?подтема 1
- ответ 62
- наибольший алфавит — тот, что в условии → при i = 6 битах — 2⁶ = 64. Спроси себя: сколько символов вмещают эти биты?подтема 3
- 30,25 байта
- оставили дробный размер записи → «не более» — вниз, «не менее» — вверх. Спроси себя: запись — целые байты?подтема 3
- 6K ≥ 104
- для 13 байт потребовали 104 бита → хватит не поместиться в 12: 6K > 96. Спроси себя: с какого K байт становится 13?подтема 4
- 128 → 7 бит
- число 128 записали 7 битами → 128 = 10000000 — 8 бит. Спроси себя: это число или номер варианта?подтема 5
- 1000 байт
- 1 Кбайт = 1000 байт → 1 Кбайт = 1024 байта. Спроси себя: какая это степень двойки?подтема 3
Итог
Тема пройдена: задача темы решена от алфавита до ответа 18. Вот что взять с собой.
- ПорядокАлфавит, биты, байты, запись, граница.
- БитыНаименьшее i, при котором 2ⁱ ≥ N.
- БайтыВверх — тому, чему их выделяют.
- Граница«Не более» — вниз, «более» и «не менее» — проверь соседа.
- Задача темыЗапись 30 байт, пароль 12 — сведения 18.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Пароль из 16 символов алфавита задачи темы. Сколько байт он займёт?
ОтветСкрыть ответ
16 · 6 = 96 бит = ровно 12 байт.
Сколько записей задачи темы по 30 байт поместится в 1 Кбайт?
ОтветСкрыть ответ
1024 // 30 = 34 — округляют вниз.
Какой наименьший алфавит требует 7 бит на символ?
ОтветСкрыть ответ
65: 64 символам хватает 6 бит, а 2⁶ + 1 = 65 — уже нет.
Пароль 90 бит и номер 9 бит. Сколько байт, если байты выделяют всей записи, и сколько — если каждой части?
ОтветСкрыть ответ
Всей записи: 99 бит → 13 байт. Частям: 12 + 2 = 14 байт.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Идентификаторы в Мбайтах
При регистрации каждому объекту присваивается идентификатор из 220 символов; символы — десятичные цифры и знаки специального алфавита из 3500 символов. Для каждого идентификатора отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Определи объём памяти в Мбайт для хранения 1 048 576 идентификаторов.
Введите число.
Подсказка
Алфавит из двух частей, целые байты — идентификатору.
Решение
N = 10 + 3500 = 3510, на символ 12 бит. Идентификатор 220 · 12 = 2640 бит = 330 байтов. 2²⁰ идентификаторов — 2²⁰ · 330 байтов = 330 Мбайт.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i per = ceil(220 * bits(10 + 3500) / 8)print(2 ** 20 * per // 2 ** 20)Ответ: 330
Сведения при 20 Кбайт
Каждому пользователю выдаётся пароль из 30 символов — заглавных латинских букв и десятичных цифр. Каждому паролю отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное. Кроме пароля, для каждого пользователя хранятся дополнительные сведения в одинаковом целом числе байтов. Для 512 пользователей потребовалось 20 Кбайт. Сколько байтов выделено дополнительным сведениям об одном пользователе?
Введите число.
Подсказка
Размер записи минус байты пароля.
Решение
Алфавит — 26 букв и 10 цифр, N = 36, 6 бит. Пароль 30 · 6 = 180 бит → 23 байта. Запись 20 · 1024 / 512 = 40 байтов, сведения 40 − 23 = 17.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i record = 20 * 1024 // 512print(record - ceil(30 * bits(36) / 8))Ответ: 17
Мощность алфавита при 3 Мбайт
Серийный номер детали состоит из 150 символов. Каждому номеру отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Для хранения 40 000 номеров отведено не более 3 Мбайт. Определи максимально возможную мощность алфавита.
Введите число.
Подсказка
«Не более»: байты на номер — целая часть.
Решение
Номер не больше 3 · 2²⁰ / 40 000 = 78,6 → 78 байтов = 624 бита. 150 · i ≤ 624, i ≤ 4,16, i = 4, наибольший алфавит 2⁴ = 16.
Решение программой
most = 3 * 2 ** 20 // 40_000 * 8 // 150print(2 ** most)Ответ: 16
Минимальная длина номера
Серийный номер содержит десятичные цифры, заглавные латинские буквы и символы из специального алфавита в 2000 символов. Каждому номеру отведено одинаковое минимально возможное целое число байтов, кодирование посимвольное, все символы кодируются одинаковым минимальным числом битов. Известно, что 5000 номеров занимают более 600 Кбайт. Определи минимально возможную длину номера.
Введите число.
Подсказка
«Более»: номер не помещается в меньшее число байтов.
Решение
N = 10 + 26 + 2000 = 2036, на символ 11 бит. 600 · 1024 / 5000 = 122,88, поэтому номер хотя бы 123 байта: код не помещается в 122 байта, 11 · K > 976, K > 88,7. Наименьшая длина 89.
Решение программой
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, 500) if 5000 * ceil(n * bits(2036) / 8) > 600 * 1024))Ответ: 89
Дополнительная информация карты
На электронной карте записаны личный код, номер подразделения и дополнительная информация. Личный код — 12 символов, каждый из которых одна из 18 разрешённых букв; код кодируется посимвольно минимальным числом битов и занимает минимальное целое число байтов. Номер подразделения — целое число от 1 до 1500, записан двоичным числом и занимает минимальное целое число байтов. Всего на карте 40 байтов данных. Сколько байтов занимает дополнительная информация?
Введите число.
Подсказка
Номер подразделения — двоичное число в своих целых байтах.
Решение
18 буквам нужно 5 бит, код 12 · 5 = 60 бит → 8 байтов. Номер до 1500 двоичным числом — 11 бит → 2 байта. Дополнительная информация: 40 − 8 − 2 = 30 байтов.
Решение программой
from math import ceil def bits(alphabet): i = 1 while 2 ** i < alphabet: i += 1 return i code = ceil(12 * bits(18) / 8)number = ceil((1500).bit_length() / 8)print(40 - code - number)Ответ: 30