Объём памяти для кодов: как решать — ОГЭ по информатике

ОГЭ Информатика сложность в тренажёре: продвинутая

Каждому из 150 товаров на складе присваивают артикул из 14 символов. В артикуле используются только 26 строчных… Объём памяти для кодов — ОГЭ по информатике, тема «Разрядность кода и мощность алфавита». Ответ проверяется на странице, разбор — сразу.

Пример 1

Каждому из 150 товаров на складе присваивают артикул из 14 символов. В артикуле используются только 26 строчных латинских букв. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый артикул хранится в одинаковом и минимально возможном целом количестве байт. Сколько байт нужно, чтобы сохранить все артикулы?

Ответ и разбор

Ответ: 1350

Символов в наборе: 26.
2⁴ = 16 < 26 < 32 = 2⁵, поэтому на символ нужно 5 бит: 4 битами кодируется только 16 символов.
Код из 14 символов: 14 · 5 = 70 бит. Целых байт нужно 9 (1 байт = 8 бит): 8 байт — это только 64 бита.
На 150 записей: 9 · 150 = 1350 байт.
Округлять до целых байт нужно каждый код: если перевести в байты только общий объём кодов (150 · 70 = 10 500 бит, в целых байтах — 1313), выйдет 1313 — меньше, чем нужно.
С 4 битами на символ вышло бы 1050, но 4 бита мало для 26 символов; если отводить на символ целый байт, вышло бы 2100 — больше, чем нужно: на символ нужно всего 5 бит.

Ответ: 1350.

Нашли ошибку? Напишите нам, код задания: oge-informatics-obyom-kodov-v-baytah-149ok16

Ещё задания этого вида — ниже. Открыть тренажёр

В 1970 году Эдгар Кодд предложил реляционную модель баз данных. Пользователь должен работать с логически связанными таблицами, не зная всех деталей размещения записей в памяти. Это разделение помогло сделать запросы к данным независимее от устройства хранилища.

Разобранный пример

Каждой из 30 посылок присваивают код отслеживания из 7 символов. В коде отслеживания используются только 10 десятичных цифр и 26 строчных латинских букв. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый код хранится в одинаковом и минимально возможном целом количестве байт. Сколько байт нужно, чтобы сохранить все коды отслеживания?

Решение

Ответ: 180

Символов в наборе: 10 + 26 = 36.
2
⁵ = 32 < 36 < 64 = 2⁶, поэтому на символ нужно 6 бит: 5 битами кодируется только 32 символа.
Код из 7 символов: 7 · 6 = 42 бита. Целых байт нужно 6 (1 байт = 8 бит): 5 байт — это только 40 бит.
На 30 записей: 6 · 30 = 180 байт.
Округлять до целых байт нужно каждый код: если перевести в байты только общий объём кодов (30 · 42 = 1260 бит, в целых байтах — 158), выйдет 158 — меньше, чем нужно.
С 5 битами на символ вышло бы 150, но 5 бит мало для 36 символов; если отводить на символ целый байт, вышло бы 210 — больше, чем нужно: на символ нужно всего 6 бит.

Ответ: 180.

Нашли ошибку? Напишите нам, код задания: oge-informatics-obyom-kodov-v-baytah-190eszn

Формулы и приём

Минимальная разрядность равномерного кода

Сколько бит нужно для равномерного кода всех символов алфавита?

2 в степени i ≥ N

i
наименьшая одинаковая длина двоичного кода символа, при которой 2 в степени i не меньше N, бит на символ
N
число разных символов алфавита; здесь N ≥ 2, символов

Двоичных слов длиной i ровно 2 в степени i. Для N разных символов нужны N различных слов одной длины; не обязательно использовать все возможные коды.
Пример: алфавит содержит 26 символов. Четырёх бит мало: 2⁴ = 16 < 26. Пяти достаточно: 2⁵ = 32 ≥ 26.
Ответ: минимально 5 бит на символ, при этом 32 − 26 = 6 кодов останутся свободными. Предполагается независимое посимвольное кодирование фиксированной длины без добавления проверочных бит.

Ловушка: равенство N = 2 в степени i требуется не всегда — кодов может быть больше, чем символов. Для неравномерного кода или хранения каждого символа в отдельном целом числе байтов расчёт другой.

Ещё примеры

Пример 2

Каждому из 300 участников олимпиады выдают регистрационный код из 6 символов. В регистрационном коде используются только 26 заглавных латинских букв, 26 строчных латинских букв и 4 специальных знака. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый код хранится в одинаковом и минимально возможном целом количестве байт. Сколько байт нужно, чтобы сохранить все регистрационные коды?

Ответ и разбор

Ответ: 1500

Символов в наборе: 26 + 26 + 4 = 56.
2
⁵ = 32 < 56 < 64 = 2⁶, поэтому на символ нужно 6 бит: 5 битами кодируется только 32 символа.
Код из 6 символов: 6 · 6 = 36 бит. Целых байт нужно 5 (1 байт = 8 бит): 4 байта — это только 32 бита.
На 300 записей: 5 · 300 = 1500 байт.
Округлять до целых байт нужно каждый код: если перевести в байты только общий объём кодов (300 · 36 = 10 800 бит, в целых байтах — 1350), выйдет 1350 — меньше, чем нужно.
С 5 битами на символ вышло бы 1200, но 5 бит мало для 56 символов; если отводить на символ целый байт, вышло бы 1800 — больше, чем нужно: на символ нужно всего 6 бит.

Ответ: 1500.

Нашли ошибку? Напишите нам, код задания: oge-informatics-obyom-kodov-v-baytah-1fbc6a2

Пример 3

Каждому из 200 товаров на складе присваивают артикул из 9 символов. В артикуле используются только 10 десятичных цифр и 3 специальных знака. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый артикул хранится в одинаковом и минимально возможном целом количестве байт. Сколько байт нужно, чтобы сохранить все артикулы?

Ответ и разбор

Ответ: 1000

Символов в наборе: 10 + 3 = 13.
2
³ = 8 < 13 < 16 = 2⁴, поэтому на символ нужно 4 бита: 3 битами кодируется только 8 символов.
Код из 9 символов: 9 · 4 = 36 бит. Целых байт нужно 5 (1 байт = 8 бит): 4 байта — это только 32 бита.
На 200 записей: 5 · 200 = 1000 байт.
Округлять до целых байт нужно каждый код: если перевести в байты только общий объём кодов (200 · 36 = 7200 бит, в целых байтах — 900), выйдет 900 — меньше, чем нужно.
С 3 битами на символ вышло бы 800, но 3 бита мало для 13 символов; если отводить на символ целый байт, вышло бы 1800 — больше, чем нужно: на символ нужно всего 4 бита.

Ответ: 1000.

Нашли ошибку? Напишите нам, код задания: oge-informatics-obyom-kodov-v-baytah-ao06op

Пример 4

Каждой из 120 посылок присваивают код отслеживания из 13 символов. В коде отслеживания используются только 26 заглавных латинских букв и 26 строчных латинских букв. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый код хранится в одинаковом и минимально возможном целом количестве байт. Сколько байт нужно, чтобы сохранить все коды отслеживания?

Ответ и разбор

Ответ: 1200

Символов в наборе: 26 + 26 = 52.
2
⁵ = 32 < 52 < 64 = 2⁶, поэтому на символ нужно 6 бит: 5 битами кодируется только 32 символа.
Код из 13 символов: 13 · 6 = 78 бит. Целых байт нужно 10 (1 байт = 8 бит): 9 байт — это только 72 бита.
На 120 записей: 10 · 120 = 1200 байт.
Округлять до целых байт нужно каждый код: если перевести в байты только общий объём кодов (120 · 78 = 9360 бит, в целых байтах — 1170), выйдет 1170 — меньше, чем нужно.
С 5 битами на символ вышло бы 1080, но 5 бит мало для 52 символов; если отводить на символ целый байт, вышло бы 1560 — больше, чем нужно: на символ нужно всего 6 бит.

Ответ: 1200.

Нашли ошибку? Напишите нам, код задания: oge-informatics-obyom-kodov-v-baytah-1f6bq98

Рядом

Продолжить тренировку

Откройте тренажёр, чтобы решать похожие задания и отслеживать прогресс по темам. Для тренажёра нужен вход; на этой странице вход не нужен.

Задание в формате экзамена с разбором

Родителю

Приложение — для ученика. Родителю ставить его не нужно: кабинет родителя открывается в браузере. Родитель видит фактическую активность, регулярность и повторяющиеся ошибки. Проверять решения самостоятельно не требуется.