Сжа́тие да́нных (англ. data compression) — алгоритмическое преобразование данных, производимое с целью уменьшения занимаемого ими объёма. Применяется для более рационального использования устройств хранения и передачи данных. Синонимы — упаковка данных, компрессия, сжимающее кодирование, кодирование источника. Обратная процедура называется восстановлением данных (распаковкой, декомпрессией).
Сжатие основано на устранении избыточности, содержащейся в исходных данных. Простейшим примером избыточности является повторение в тексте фрагментов (например, слов естественного или машинного языка). Подобная избыточность обычно устраняется заменой повторяющейся последовательности ссылкой на уже закодированный фрагмент с указанием его длины. Другой вид избыточности связан с тем, что некоторые значения в сжимаемых данных встречаются чаще других. Сокращение объёма данных достигается за счёт замены часто встречающихся данных короткими кодовыми словами, а редких — длинными (энтропийное кодирование). Сжатие данных, не обладающих свойством избыточности (например, случайный сигнал или белый шум, зашифрованные сообщения), принципиально невозможно без потерь.
Сжатие без потерь позволяет полностью восстановить исходное сообщение, так как не уменьшает в нем количество информации, несмотря на уменьшение длины. Такая возможность возникает только если распределение вероятностей на множестве сообщений не равномерное, например часть теоретически возможных в прежней кодировке сообщений на практике не встречается.
Примечание:
Если к числу в двоичной системе счисления приписывать в конец цифры, то число увеличивается и никак не может уменьшится. Поэтому, n<f(n). Следовательно, перебор различных чисел, принадлежащих отрезку [90;160], можно смело ставить до 160 (можно и меньше, но лень расписывать вычисления).
ToBinary - функция перевода числа из десятичной СС в двоичную. Можно писать любой алгоритм, необязательно в точности использовать мой.
FromBinary - функция перевода числа из двоичной СС в десятичную. Можно писать любой алгоритм, необязательно в точности использовать мой.
func - функция, которая выполняет преобразования числа согласно условию (пункты 1, 2, 3, 4).
Код кажется большим только из-за процедур и begin/endов. Без них - всего то 7 строчек :). В скринах можно проверить, действительно ли 19 (40-22+1).
Пример работы:
Если робот в системе Кумир, то вот такая программа:
использовать Робот
алг
нач
нц пока справа стена
вниз
кц
нц
вправо
кц при сверху свободно
вверх
нц
влево
закрасить
кц при слева стена
кон