Задание 5: кодирование и длина кода

Что проверяет задание 5

В задании 5 легко потерять баллы не из-за сложной математики, а из-за спешки: перепутать длину кода с количеством символов или неверно посчитать варианты. Здесь ты научишься быстро определять, сколько бит занимает сообщение, сколько символов можно закодировать и как находить неизвестную длину кода.

Обычно в условии говорится, что каждому символу некоторого алфавита соответствует код фиксированной длины. Например, один символ записывается четырьмя битами. Тогда длина сообщения зависит от количества символов, а число возможных кодов — от длины одного кода.

Важно различать три величины:

• размер алфавита — сколько разных символов используется;
• длина кода одного символа — сколько бит или знаков занимает код;
• длина всего сообщения — сколько бит занимает последовательность символов.

Задания этой темы встречаются в вариантах ЕГЭ по информатике и требуют не столько вычислений, сколько внимательного чтения условия.

Главная формула: степени двойки

Если код состоит из n бит, каждый бит может иметь одно из двух значений: 0 или 1. Поэтому число различных кодов вычисляется так: 2ⁿ. Например, из двух битов можно составить 2² = 4 кода: 00, 01, 10 и 11.

Если нужно закодировать M разных символов, длина кода n должна удовлетворять условию 2ⁿ ≥ M. Знак ≥ важен: кодов может быть больше, чем символов, но их должно хватать для всех символов алфавита.

Ищи наименьшее подходящее n. Полезно держать в памяти ряд степеней двойки:

\( 2^1 = 2 \)
\( 2^2 = 4 \)
\( 2^3 = 8 \)
\( 2^4 = 16 \)
\( 2^5 = 32 \)
\( 2^6 = 64 \)
\( 2^7 = 128 \)
\( 2^8 = 256 \)

Если в алфавите 20 символов, трёх бит недостаточно, потому что 2³ = 8, а четырёх достаточно: 2⁴ = 16 тоже мало, значит нужен код длиной 5 бит, ведь 2⁵ = 32.

Как находить длину сообщения

Если каждый символ имеет код длиной n бит, а сообщение содержит k символов, общая длина равна k × n бит. Пробелы, знаки препинания и переходы строки учитываются, только если они названы символами сообщения.

Например, слово из 12 символов при коде длиной 5 бит занимает 12 × 5 = 60 бит. Если ответ требуется в байтах, раздели количество бит на 8. Если число не делится на 8, внимательно проверь условие: возможно, требуется минимальное число целых байтов. Тогда используется округление вверх.

Для перевода единиц используй соотношения:

1 байт = 8 бит
1 Кбайт = 1024 байта
1 Мбайт = 1024 Кбайта

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

Удобная таблица помогает не перепутать направление вычислений:

Что известно	Что найти	Действие
k символов и n бит на символ	всю длину	k × n
вся длина и n бит на символ	число символов	длина ÷ n
M символов алфавита	минимальный n	найти 2ⁿ ≥ M

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

Рассмотрим типичную задачу. В алфавите 30 символов, каждый символ кодируется одинаковым количеством бит. Сообщение состоит из 18 символов. Найдём минимальную длину сообщения в битах.

1. Нужно закодировать 30 символов.
2. Ищем минимальное n: 2ⁿ ≥ 30.
3. 2⁴ = 16, этого недостаточно.
4. 2⁵ = 32, этого достаточно.
5. Один символ занимает 5 бит.
6. В сообщении 18 символов.
7. Общая длина: 18 × 5 = 90 бит.
Ответ: 90.

Обрати внимание: нельзя взять 4 бита только потому, что это ближайшая степень двойки. Четыре бита дают 16 кодов, а символов 30. Неиспользованные коды допустимы, но нехватка кодов невозможна.

Если бы вопрос просил указать объём в байтах, 90 бит пришлось бы перевести в байты. Полных байтов это 11, но для хранения всех 90 бит потребуется 12 байт, потому что 11 байт содержат только 88 бит.

Для самостоятельной практики можно открыть бесплатную практику в личном кабинете и решить несколько задач на степени двойки, перевод единиц и длину сообщения.

Типичные ошибки и проверка ответа

Первая ошибка — использовать формулу 2 × n вместо 2ⁿ. Биты не складываются по два: каждый новый разряд вдвое увеличивает число возможных кодов.

Вторая ошибка — выбирать не минимальную, а любую подходящую длину. Если 2⁶ ≥ M и 2⁷ тоже ≥ M, нужен ответ 6, потому что спрашивается минимальное число бит.

Третья ошибка — забывать о самом сообщении. Число символов алфавита определяет код одного символа, но не длину всей записи. После нахождения n проверь, сколько символов действительно дано.

Четвёртая ошибка — считать только буквы, хотя в условии сказано, что пробел тоже является символом. Всегда выписывай состав сообщения буквально.

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

Что запомнить

Код длиной n бит даёт 2ⁿ различных комбинаций. Для алфавита из M символов выбирай наименьшее n, при котором 2ⁿ ≥ M. Длина сообщения из k символов при фиксированном коде равна k × n бит.

Если встречаются байты, помни: 1 байт = 8 бит. При переводе битов в целые байты для хранения обычно требуется округление вверх. Если код переменной длины не упомянут, не усложняй решение: считай, что длина кода каждого символа одинакова.

Твой алгоритм: выписать размер алфавита, подобрать степень двойки, умножить длину кода на число символов, проверить единицы измерения и только затем выбрать ответ.

Следующий шаг — зарегистрируйся и реши 5 заданий бесплатно в личном кабинете. Так ты сразу увидишь, на каком этапе чаще всего возникает ошибка.