Профильная информатика:
подготовка к ЕГЭ и олимпиадам

1 2 3 4 5 6 7 8 9 10^Р 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

Для хранения длинных чисел можно использовать алгоритм кодирования повторов (RLE), который заменяет повторяющиеся цифры (серии) на число повторов цифры и саму цифру. Например, число 5999 после сжатия станет числом 1539. Если длина серии превосходит 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\) байт.

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