Вариант № EGE_INF_1801
Добавлен 13 октября 2017 г. в 1:51. Изменён 15 июня 2018 г. в 1:20.
Задание
Для хранения строк, содержащих только заглавные буквы латинского алфавита, можно использовать алгоритм кодирования повторов (RLE), который заменяет повторяющиеся буквы (серии) на число повторов этой буквы и саму букву.
Положительные числа используют для записи количества повторов одной буквы, а отрицательные — для записи количества неодинаковых букв, следующих друг за другом.
Если длина серии превосходит 16, она разбивается на несколько серий длиной 16 и, возможно, ещё одну длиной меньше 16.
Например, строка ABDDD
после сжатия примет вид -2AB3D
.
После сжатия производится поразрядное кодирование, все числа и символы кодируются одинаковым и минимально возможным количеством бит.
Сколько байт потребуется для сжатия и кодирования указанным способом строки BCBAAAAAAAAAAAEEE
?
Решение
После сжатия указанным способом исходной строки BCBAAAAAAAAAAAEEE
будет получена строка -3BCB11A3E
.
Всего возможны 32
варианта длин серии (от -16
до 16
, не включая число 0
).
Следовательно, для кодирования длины каждой серии достаточно выделить 5
бит.
Для кодирования каждой из 26
букв латинского алфавита также достаточно выделить 5
бит.
Таким образом, в сжатой строке -3 B C B 11 A 3 E
имеются 3
длины серий (-3, 11
и 3
) и 5
букв (B, C, B, A, E
).
Следовательно, для кодирования сжатой строки потребуется 3 * 5 + 5 * 5 = 40
бит = 5
байт.
Ответ
5
Подробнее...