Задание №1702/13
Задание
Для хранения длинных чисел можно использовать алгоритм кодирования повторов (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\) байт.
Подробнее...Ответ
6
Подробнее...
Добрый вечер, Katerina! Цифра 1 встречается 1 раз, поэтому пишем 11, потом цифра 2 встречается тоже 1 раз, следовательно, пишем 12. Аналогично с тройкой, а вот 0 встречается 11 раз, поэму разбиваем эту серию на две - из девяти нулей и из двух нулей и получаем 90 и 20 соответственно.
Здравствуйте! Скажите, пожалуйста, откуда берётся число 11 перед 1213902035
Доброе утро, Александр! Да, наверное надо было немного изменить пример. Я его изменил вначале здесь http://ege-inf.ru/variants/1702/13, но теперь и тут поправил. Так что, надеюсь, проблема решена.
Велика вероятность допущения ошибки, так как в задаче говорится, что замена производится в серии повторяющихся цифр (то есть, можно посчитать, что те цифры, которые не повторяются, не нуждаются в росписи на количество)
Здравствуйте, Егор! Да, с одной стороны Вы правы, для кодирования шести символов бит нужно меньше. Но мы же кодируем общий случай, заранее не зная, какие символы могут быть, а какие нет. Аналогично рассуждая, в русском языке редко встречается "Ъ", но он есть в любом шрифте. В этом и есть смысл "алфавитного подхода" - пронумеровать и закодировать равномерным кодом (т.е. количество бит на каждый символ одинаковое).
В решении написано N = 10, но разве в числе 111213902035 используется десять цифр? 0 1 2 3 5 9 - все, что там используются, их 6 и закодировать их можно всего 3 битами, а не 4. Я прав или нет?
Ирина, спасибо за замечание! В будущих вариантах буду использовать предложенную Вами формулировку: "... который заменяет повторяющиеся цифры (серии) на число повторов цифры и саму цифру".
По поводу некорректности длины серии уже говорили, но и еще одна неточность: пример конфликтует с определением. "999 станет числом 93" или "заменяет серию на число повторов цифры и ее саму"
Светлана, добрый вечер!
Да, на сайте опечатка, Вы правы. Спасибо!
Здравствуйте! А разве количество нулей всего 10, а не 11, т.е. после сжатия получим в части нулей 9020?
Здравствуйте, Павел!
Замечание очень ценное, спасибо! Обязательно учту в будущих вариантах. Имеющиеся варианты решил всё-таки не трогать (иначе их придётся улучшать бесконечно и не останется времени на создание новых).
Исправить"например" на число 5999 тогда получится 1539 и становится понятно, что серии могут иметь длину =1
Здравствуйте, Лариса! Спасибо за замечание. Согласен, что формулировка задания далека от идеала. В будущих вариантах подумаю, как её можно улучшить.
Здравствуйте. Я думаю, что в условии где то должно указываться на то, что серия имеет длину от 1 до N, то есть при кодировании этим способом одна цифра рассматривается тоже как серия или рассмотреть пример. Задача интересная, спасибо.