Подготовка к ЕГЭ и олимпиадам по информатике 2020 / Тренировочные варианты ЕГЭ

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

Вариант № EGE_INF_1801

Добавлен 13 октября 2017 г. в 1:51. Изменён 15 июня 2018 г. в 1:20.Скачать PDF

Задание

Для хранения строк, содержащих только заглавные буквы латинского алфавита, можно использовать алгоритм кодирования повторов (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

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