Не забывайте подписываться на канал! Таким образом вы помогаете выходу новых разборов!
№ 623 Джобс 02.11.2020 (Уровень: Сложный)
Для хранения длинных чисел можно использовать алгоритм кодирования повторов (RLE), который заменяет повторяющиеся цифры (серии) на одну цифру и число её повторов. Например, число 5999 после сжатия станет числом 1539. Если длина серии превосходит 9, она разбивается на несколько серий длиной 9 и, возможно, ещё одну длиной меньше 9 . После сжатия производится поразрядное кодирование, все цифры кодируются одинаковым и минимально возможным количеством бит. Сколько байт потребуется для сжатия и кодирования указанным способом числа 12300000000000555?
Аналитически:
1. Применение алгоритма RLE (Run-Length Encoding)
Исходное число: 12300000000000555
Разобьём его на серии повторяющихся цифр:
- 1 → 1 раз
- 2 → 1 раз
- 3 → 1 раз
- 0 → 11 раз (разбиваем на две серии: 90 и 20)
- 5 → 3 раза
Таким образом, после сжатия получаем:
1 1 2 1 3 1 9 0 2 0 5 3
(каждая пара чисел: [количество повторов] [цифра])
2. Поразрядное кодирование
- Всего цифр после сжатия: 12 (6 пар чисел).
- Максимальная цифра в сжатом числе: 9 (в паре 9 0).
- Для кодирования цифр от 0 до 9 требуется: log2(10)=4 бита на цифру.
3. Общий объём данных
- Всего цифр: 12
- Бит на цифру: 4
- Общее количество бит: 12×4=48 бит.
- Переводим в байты: 48/8=6 байт.
Если вам понравился разбор - можете поддержать автора с помощью функции "доната". Спасибо
Если у вас остались вопросы, хотите разобраться, хотите подготовиться к ЕГЭ/ОГЭ по информатике или изучить программирование на языке Python - добро пожаловать на пробный урок в телеграм t.me/MikhailRomanov
А также ставьте лайк, пишите комментарии.
ЖМИ НА ССЫЛКУ СНИЗУ ДЛЯ НАВИГАЦИИ ПО РЕШЕНИЯМ
Тут все разборы собраны воедино