Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!
№ 576 Джобс 26.10.2020 (Уровень: Сложный)
Текст, содержащий строчные и заглавные буквы английского и русского алфавитов, десятичные цифры и 15 различных знаков, кодируется двумя способами с предварительным составлением кодировочной таблицы, используемой в обоих случаях.
1. С использованием равномерного кода с минимальной длиной. Все символы кодируются с помощью двоичного кода одинаковой для всех символов длины минимально возможной для заданного набора. Коды символов записываются друг за другом с начала файла без разделителей.
2. С использованием неравномерного кода. Сначала в файл записывается словарь вида: 1 Байт – номер символа в кодировочной таблице из варианта 1, 2
Байта – двоичный код символа, 1 Байт – количество бит из кода, используемое для кодирования. Например, двоичная запись 00110010 00000010 00101101 00001010 означает, что 50 символ таблицы кодируется последовательностью 1000101101 (10 бит из двухбайтовой записи). Затем записываются все коды символов в тексте подряд без разделителей. Известно, что средняя длина кода для текста из 100 символов – 600 бит.
Определите, сколько символов (в сотнях) должно быть в тексте, чтобы использование второго метода было эффективнее по используемой для хранения текста памяти.
Примечание: в русском алфавите 33 буквы, в английском – 26.
Аналитически:
1. Определение мощности алфавита и размера кодировочной таблицы
Алфавит содержит:
- Строчные и заглавные буквы английского алфавита:
26×2=52 символа. - Строчные и заглавные буквы русского алфавита:
33×2=66 символов. - Десятичные цифры:
1010 символов. - 15 различных знаков.
Общее количество символов:
52+66+10+15=14352+66+10+15=143 символа.
2. Равномерное кодирование (метод 1)
- Количество бит на символ:
log2(143)=8 бит (так как 2^7=128<143≤256=2^8). - Размер кода для текста из N символов:
8N бит = N байт.
3. Неравномерное кодирование (метод 2)
- Словарь кодов:
Каждый символ описывается 1+2+1=4 байтами.
Всего словарь занимает 143×4=5722 байта. - Кодирование текста:
Средняя длина кода на символ: 600 / 100=6 бит.
Для текста из N символов: 6N бит = 6N / 8 байт.
4. Условие эффективности метода 2
Метод 2 эффективнее, если его общий размер меньше, чем в методе 1:
572+6N/8<N.
Упростим неравенство (пренебрегая округлением):
572+0.75N<N⇒572<0.25N⇒N>2288.
Так как N измеряется в сотнях символов:
N>22.88⇒N≥23 сотни.
5. Проверка для N=23 сотни (2300 символов)
- Метод 1:
23002300 байт. - Метод 2:
Словарь: 572 байта.
Текст: (6×2300)/8=1725 байт.
Всего: 572+1725=2297 байт <2300 байт.
6. Ответ
Метод 2 становится эффективнее при 23 сотнях символов (2300 символов).
Если вам понравился разбор - можете поддержать автора с помощью функции "доната". Спасибо
Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov
А также ставьте лайк, пишите комментарии.
ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ
Тут все разборы собраны воедино