DVBogdanov.ru / Тренировочный вариант по информатике, задание 13


Задание №1702/13

Задание

Для хранения длинных чисел можно использовать алгоритм кодирования повторов (RLE), который заменяет повторяющиеся цифры (серии) на одну цифру и число её повторов. Например, число 999 после сжатия станет числом 39. Если длина серии превосходит 9, она разбивается на несколько серий длиной 9 и, возможно, ещё одну длиной меньше 9. После сжатия производится поразрядное кодирование, все цифры кодируются одинаковым и минимально возможным количеством бит.

Сколько байт потребуется для сжатия и кодирования указанным способом числа 12300000000000555?

Решение

После сжатия исходное число примет следующий вид: \[12\,300\,000\,000\,000\,555\ \rightarrow 11\,12\,13\,90\,20\,35.\]

Для кодирования каждой цифры требуется \(i = \left\lfloor \log_{2}N \right\rfloor \), где операция \(\left\lfloor\,\right\rfloor \) обозначает округление вверх до ближайшего целого. Так как всего имеется \(N=10\) десятичных цифр, получим \(i = \left\lfloor \log_{2}{10} \right\rfloor = 4\).

Таким образом, для кодирования числа \(11\,12\,13\,90\,20\,35\) потребуется \(4 \cdot 12 = 48\) бит или \(48 / 8 = 6\) байт.

Подробнее...

Ответ

6

Подробнее...
Добавить комментарий
Комментарии (10)
#Алгоритм кодирования повторов RLE #Алгоритмы сжатия #Алфавитный подход #Задачи на кодирование информации #Кодирование текста #Определение количества информации #Подготовка к ЕГЭ по информатике #Равномерное кодирование