Сжатие строки

← →
SniZ © (2005-06-09 00:13) [0]

привет всем, подскижите как сжать строку, вернее есть набор символов в файле, ну типа вот:
uuuuuuuuuuuusssuuuuuuuuueeeeeennnnnuueeeeeee

затем нужно типа сжать это все в виде таком: (r)S, где r -количество символов, не меньшее 3, а S - символ, кароче нужно преобразовать эту строку в :
(12)u(3)s(9)u(6)e(5)nuu(7)e
а там где меньше трёх символов, просто оставлять, не трогать,
помогите плиззз

← →
Lenka © (2005-06-09 00:22) [1]

← →
Eraser © (2005-06-09 00:22) [2]

SniZ © (09.06.05 00:13)

Используй Zlib, имеется в комплекте с делфи.

← →
SniZ © (2005-06-09 00:24) [3]

нет, файл вывода должен быть таким как я написал, а вот подсчитать не магу, не умею, гы,

← →
Eraser © (2005-06-09 00:28) [4]

SniZ © (09.06.05 00:24) [3]

Ну дык в чём проблема?
Должно выглядеть примерно так:
if s[i] <> s[i + 1] then
...
else
...

← →
Просто Джо © (2005-06-09 00:38) [5]

> а вот подсчитать не магу, не умею, гы,

С этим -- в школу, там учат считать.

← →
SniZ © (2005-06-09 00:54) [6]

уууу, блин, ыыы, завтра сдавать....

← →
Gero © (2005-06-09 00:58) [7]

> уууу, блин, ыыы

Ну ты же не в зоопарке.

← →
SniZ © (2005-06-09 01:04) [8]

да сорри, просто завтра лаб-раб сдавать

← →
Юрий Зотов © (2005-06-09 01:13) [9]

> SniZ

Вот решение, точно соответствующее Вашей постановке задачи:
function PackString(S: string): string; function GetChainLength(const S: string): integer; begin Result := 0; while (Result < Length(S)) and (S[Result + 1] = S[1]) do Inc(Result) end; var Len: integer; begin Result := ""; Len := GetChainLength(S); while Len > 0 do begin if Len > 2 then Result := Result + Format("(%d)%s", [Len, S[1]]) else Result := Result + Copy(S, 1, Len); Delete(S, 1, Len); Len := GetChainLength(S) end end;

Но имейте в виду 2 вещи.

1. Преподаватель - не дурак. О том, что существуют подобные форумы он прекрасно знает. Еще по стилю кода он обязательно поймет, что написан этот код вовсе не новичком. Поэтому вряд ли Вам удастся защитить работу, если Вы досконально не разберетесь буквально в каждой букве кода - что это, зачем оно нужно и почему сделано именно так, а не иначе.

2. Ваша постановка задачи содержит погрешность, из-за которой сжатая строка не получается минимальной, она могла бы быть и меньше. Поскольку код точно соответствует постановке задачи, то он, естественно, содержит ту же самую погрешность. Вам нужно найти и исправить эту погрешность самостоятельно, иначе Вы тоже вряд ли сумеете защитить работу.

← →
Defunct © (2005-06-09 01:19) [10]

> Юрий Зотов

ну прям-таки барские наставления. ;>
PCX давно отрытый формат ;>

← →
SniZ © (2005-06-09 01:25) [11]

большое спасибо, код прекрасный, но он попросил только прогу
ыыы, повезло

← →
Юрий Зотов © (2005-06-09 01:31) [12]

> Defunct © (09.06.05 01:19) [10]

> ну прям-таки барские наставления.

Я рад, что Вам понравилось, но Вы скромно забыли добавить "ИМХО". Пожалуйста, не забывайте об этом, ладно? А то прям-таки барство какое-то с Вашей стороны получается. ИМХО.

Еще одно мое ИМХО такое: код дан, как выход из тупика, но не как выход из ситуации - так что человеку все же придется поработать самостоятельно (что, собственно, от него и требовалось). Просто теперь у него есть над чем работать, вот и вся разница.

> PCX давно отрытый формат

Это уже интереснее. А кто ж его отрыл?

← →
Defunct © (2005-06-09 01:41) [13]

Юрий Зотов © (09.06.05 01:31) [12]

Прошу прощения, если Вам мой юмор не понравился.
Только что с "пива" так, что мог чего-то не то сболтнуть.
Но право же наставления мне понравились. Ничего личного.

Скромно, добавляю свою "imho"

> Это уже интереснее. А кто ж его отрыл?
Честно говоря, я думал Вы прекрасно знакомы с PCX форматом, в котором, для кодирования длины цепочки ипользуются значения байта от 224 до 255 (224 - 1, 225 - 2 и т.д). Если же символ встречается однократно, тогда длина просто не ставится, если символ больше либо равен 224, тогда кодируется двумя символами (224:код символа). Стандартный PCX формат.

← →
Юрий Зотов © (2005-06-09 01:46) [14]

> Defunct © (09.06.05 01:41) [13]

> Стандартный PCX формат.
Это да. Но кто ж его отрыл?
:о)

← →
Defunct © (2005-06-09 01:51) [15]

Юрий Зотов © (09.06.05 01:46) [14]

Простите мое невежество, я не помню фамилии авторов. Поэтому не могу сказать кто его открыл. Имел в виду, что формат такого кодирования является открытым - "свободным для использования и модификации в своих приложениях" в отличие от RAR и т.п.

← →
jack128 © (2005-06-09 02:05) [16]

Defunct © (09.06.05 1:51) [15]
Имел в виду, что формат такого кодирования является открытым - "свободным для использования и модификации в своих приложениях" в отличие от RAR
Гм.. Вроде как формат не может быть запотентован.. Так что любое приложение может использовать формат рар"а если смеет его взломать. Под открытым/закрытым форматом обычно имеется в виду наличие документации на него..

← →
Юрий Зотов © (2005-06-09 02:35) [17]

> Defunct © (09.06.05 01:51) [15]

> не могу сказать кто его открыл.

Так я и не об этом спрашивал. А о том, кто его отрыл.
:о)

← →
Просто Джо © (2005-06-09 03:29) [18]

МЕГАЛОЛ, ребята :)

← →
Alx2 © (2005-06-09 09:27) [19]

>Юрий Зотов © (09.06.05 01:13)

Затраты по памяти ~ 2*n+a, по времени ~ 3*n+b где n - длина входа, "a" и "b" не зависят от n.

Конечно, пример учебный и наглядность - основное.

Но потом так все и останется, имхо.

Красота стоит жертв?

← →
SniZ © (2005-06-09 14:22) [20]

всеравно спасибочки, я уже наколбасил 9 заданий, а вот на эту задачу уже мозгов вечером не хватало, но благодаря вам я сделал это! всем спасибо!

← →
BFG9k © (2005-06-09 15:09) [21]

Юрий Зотов :
> 1. Преподаватель - не дурак.

Был бы не дурак , не стал бы работать преподом информатики :)

← →
Суслик © (2005-06-09 15:14) [22]

> [9] Юрий Зотов © (09.06.05 01:13)

> 2. Ваша постановка задачи содержит погрешность,

Юр, чессо слово, не могу понять, что ты углядел в постановке задачи. Разъясни мне плиз?

← →
-=XP=- © (2005-06-09 15:15) [23]

я б сделала так: просто подсчитать количество одинаковых букв подряд, если их больше 3 тогда записать в новую строку в скобках количество плюс прилепить сам символ, а если меньше трех, тогда просто переписать в ту новую строку.

Вот интересно, что получится в результате "упаковки" такой строки: "фффнаааикккчцццешшшгуууо".

:о)

← →
-=XP=- © (2005-06-09 15:18) [24]

Юр, чессо слово, не могу понять, что ты углядел в постановке задачи. Разъясни мне плиз?

Извините, что вмешиваюсь.

йййцццууу
даст
(3)й(3)ц(у)

Я не рискнул бы назвать это сжатием, а лучше заменил бы число 3 на 4.

← →
-=XP=- © (2005-06-09 15:19) [25]

йййцццууу (3)й(3)ц(3)у

P.S. Еще раз прошу прощения.

← →
Суслик © (2005-06-09 15:22) [26]

> [24] -=XP=- © (09.06.05 15:18)

> Я не рискнул бы назвать это сжатием

Да это понятно, что в некоторых случаях строка становится длиннее. Но заданию то соответсвтует. Зачем называть погрешностью, то что является особенностью задания.

Я тут подумал, что ЮЗ увидел, что-то более тонкое.

Я тут подумал, что ЮЗ увидел, что-то более тонкое.

Например, строка "Сожмите меня в (2) раза" ;)

я подумал, что он увидел логическую ошибку в задании.

В каком контексте, что-то я не пойму?
Есть какие-то мысли? ;)

> [29] -=XP=- © (09.06.05 15:47)

> В каком контексте, что-то я не пойму?
> Есть какие-то мысли? ;)

Мыслей нет. Но Юра просто так не говорит.

> Суслик

Помоему очевидно.
> не меньшее 3
более трех. (вот она "маленькая погрешность" всего то в знаке >= и > )

Что будет в результате "сжатия" такой строки:

"((("

В простонародии это называется RLE

см. [27]
поскольку обратного алгоритма "разжатия" не существует, то можно было сразу до 1 байта ужимать. или до нуля.

Вопрос об эффективности или других форматах не стоит. Не надо путать дидактику и прочее.
Это задание на определение знаний учащего и развития навыков программирования в части разработки алгоритмов.
Задание должно быть выполнено самостоятельно и в соответствии с постановкой, кроме того желательно правильно, но не обязательно.

>Anatoly Podgoretsky © (10.06.05 09:41) [34]

>Не надо путать дидактику и прочее.

Не согласен. Только как сочетать "дидактику и прочее" - не знаю :(

> Суслик

Думай как хочешь, очевидное от этого неизменится.

Сжатие строки Найти похожие ветки