 |
Нетривиальная задача |
 |
06.11.2003, 18:16
|
#1
|
|
4294967296
Join Date: 03 2002
Location: /proc/1
Age: 40
Posts: 379
Rep Power: 0
|
Нетривиальная задача
Дана строка типа:
AAAAAAAAAABABABCCD
Нужно упаковать повторяющиеся подстроки так чтобы кол-во символов в результирующей строке было минимальным.
Т.е. если на входе : AAAAAAAAAABABABCCD
то на выходе должно быть : 9(A)3(AB)CCD
Обратите внимание на то, что если бы CCD превратилось в
2(C)D то результирующая строка стала бы длинее ( т.е. скобки и числа в результирующей строке тоже считаются символами ).
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))
Что скажете  ?
Boyov.
__________________
Free your mind and your OS will follow
|
|
|
|
|
06.11.2003, 18:51
|
#2
|
|
Академик
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 53
Posts: 4,854
Rep Power: 5
|
A zazipovat` slabo ? LZW compressiey 
Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.
__________________
Женщин не надо понимать, их надо любить! 
|
|
|
|
|
06.11.2003, 19:42
|
#3
|
|
Banned
Join Date: 10 2002
Location: Brooklyn, New York
Age: 47
Posts: 3,760
Rep Power: 0
|
u vas kursovaya da?
p.s. Vas ne Armen sluchaino zvat'?
|
|
|
|
|
06.11.2003, 20:01
|
#4
|
|
инсценирующи
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 39
Posts: 4,327
Rep Power: 5
|
Quote:
Originally posted by DaNYer
u vas kursovaya da?
p.s. Vas ne Armen sluchaino zvat'?
|
Не, Карен, у нас олимпиада
И зовут его Артемом
__________________
...ибо...
Rgrdz. [ Кселджэн ]
|
|
|
|
|
06.11.2003, 23:01
|
#5
|
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 55
Posts: 3,118
Rep Power: 0
|
Quote:
Originally posted by W_z_rd
A zazipovat` slabo ? LZW compressiey
Zadacha na samom dele trivialnaya, esli znat` teoriyu po compressii.
|
lzw ne katit t.k. zdes' buffery mogut byt' wlozhennymi - wot eto primer .....
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))
nu wo wsjakom sluchae ne katit w original'nom wariante, a tak -mozhno peredelat'
|
|
|
|
|
06.11.2003, 23:16
|
#6
|
|
4294967296
Join Date: 03 2002
Location: /proc/1
Age: 40
Posts: 379
Rep Power: 0
|
Quote:
Originally posted by W_z_rd
A zazipovat` slabo ? LZW compressiey .
|
А смысл ??? 
LZW это конечно хорошо ( http://dogma.net/markn/articles/lzw/lzw.htm), а ещё существует туева хуча всяких других способов "compression"-а (md5 например http://www.faqs.org/rfcs/rfc1321.html) ,но я не думаю что эта задача вот так просто решится с помощю какого-то конкретного (известого) алгоритма. Correct me in case I'm wrong. Буду very very happy если я неправ
All the best
Boyov.
__________________
Free your mind and your OS will follow
|
|
|
|
|
07.11.2003, 02:13
|
#7
|
|
Академик
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 53
Posts: 4,854
Rep Power: 5
|
Quote:
Originally posted by nm
lzw ne katit t.k. zdes' buffery mogut byt' wlozhennymi - wot eto primer .....
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))
nu wo wsjakom sluchae ne katit w original'nom wariante, a tak -mozhno peredelat'
|
So vlozhennymi ciklami interesnee. Konechno, ya ne imel vvidu LZW v original`nom variante. Eto bila shutka s izryadnoy doley pravdi: mozhno ispolzovat` idei lezhashie v osnove LZW i podobnix kompressiy.
To Boyov:
MD5 eto hash-funkciya (message digest), a ne compressiya. No eto nevazhno. Ne, ti prav, gotovix sposobov netu, no sm. vishe.
__________________
Женщин не надо понимать, их надо любить!
|
|
|
|
|
07.11.2003, 08:07
|
#8
|
|
Академик
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Rep Power: 6
|
s kakix por MD5 stal "compression" -om ?
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
|
|
|
|
|
07.11.2003, 08:19
|
#9
|
|
Академик
Join Date: 09 2001
Location: inside myself
Posts: 5,369
Rep Power: 6
|
eta zadacha - PCX-compression.
t.e. graficheskij format PCX.
a smysl topika ya ne ponyal - algoritm napisat'?
__________________
И повешенные могут качаться в неположенную сторону. /С.Е.Лец/
|
|
|
|
|
07.11.2003, 12:32
|
#10
|
|
инсценирующи
Join Date: 07 2002
Location: Fireplace of Ecotopia
Age: 39
Posts: 4,327
Rep Power: 5
|
Quote:
Originally posted by Greco El
a smysl topika ya ne ponyal - algoritm napisat'?
|
если не написать, то хотя бы описать
__________________
...ибо...
Rgrdz. [ Кселджэн ]
|
|
|
|
|
07.11.2003, 13:21
|
#11
|
|
4294967296
Join Date: 03 2002
Location: /proc/1
Age: 40
Posts: 379
Rep Power: 0
|
Quote:
Originally posted by Greco El
s kakix por MD5 stal "compression" -om ?
|
Народ ,пардон, но вы меня не так поняли . It was a Joke . Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.
O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.
Boyov
__________________
Free your mind and your OS will follow
|
|
|
|
|
07.11.2003, 13:51
|
#12
|
|
Академик
Join Date: 08 2002
Location: Yerevan, Armenia
Age: 53
Posts: 4,854
Rep Power: 5
|
Quote:
Originally posted by Boyov
Народ ,пардон, но вы меня не так поняли . It was a Joke . Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.
O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.
Boyov
|
Shyutnik !
Udachi !
__________________
Женщин не надо понимать, их надо любить!
|
|
|
|
|
Re: Нетривиальная задача |
|
|
07.11.2003, 15:18
|
#13
|
|
Бакалавр
Join Date: 03 2002
Location: Detroit, MI, USA
Posts: 482
Rep Power: 0
|
Re: Нетривиальная задача
Quote:
Originally posted by Boyov
Дана строка типа:
AAAAAAAAAABABABCCD
Нужно упаковать повторяющиеся подстроки так чтобы кол-во символов в результирующей строке было минимальным.
Т.е. если на входе : AAAAAAAAAABABABCCD
то на выходе должно быть : 9(A)3(AB)CCD
Обратите внимание на то, что если бы CCD превратилось в
2(C)D то результирующая строка стала бы длинее ( т.е. скобки и числа в результирующей строке тоже считаются символами ).
Вот ещё один пример:
Вход: NEERCYESYESYESNEERCYESYESYES
Выход: 2(NEERC3(YES))
Что скажете ?
Boyov.
|
A esli primenit' vesovuyu funkciyu? Tipa
F(X) = number of elements in compressed x. Sootvetstvenno, iskat' min x.
Naprimer F(CCD) = 4, sledovatel'no, CCD ne kompressiruem. F(AAAAAAAAAA) = 4 - kompressiruem.
__________________
Hovhannes Tumanyan,
CISSP
|
|
|
|
|
08.11.2003, 18:02
|
#14
|
|
ЙЦУКЕН
Join Date: 07 2002
Location: 0x68,0x69,0x72, 0x69,0x6e,0x67, 0x20,0x6e,0x6f, 0x77
Age: 55
Posts: 3,118
Rep Power: 0
|
Quote:
Originally posted by Boyov
Народ ,пардон, но вы меня не так поняли :). It was a Joke ;). Я знаю что такое md5, просто я имел ввиду что LZW (хоть это и алгоритм сжимания) не решает данную задачу.
O смысле данного топика: мне нужен был ,скажем так, guidance, и я кстати его получил. Всем Спасибо.
Boyov
|
kstati naschet LZ - esli ja prawil'no ponimaju, tebe nuzhno na Ziv-e gonjat' LZ algoritm, rekursiwno ....
chtob i w Ziv-e najti powtorjajushiesja stroki ...
a washe eto wse ne effektiwno :)))
kstati kakie ogranichenija es't ? na ozu, wremja wypolnenija ?
|
|
|
|
|
08.11.2003, 19:00
|
#15
|
|
4294967296
Join Date: 03 2002
Location: /proc/1
Age: 40
Posts: 379
Rep Power: 0
|
Quote:
Originally posted by nm
a washe eto wse ne effektiwno ))
?
|
A chto sobstvenno effectivno ???
Quote:
Originally posted by nm
kstati kakie ogranichenija es't ? na ozu, wremja wypolnenija ? [/B]
|
Vot original'naya zadacha
http://neerc.ifmo.ru/past/2002/problems/folding.htm
Tam ob ogranicheniyax vaabshe ne skazano, (eto otnositsya i ko vsem ostal'nim zadacham 2002 goda) ,navernoe nado polagat' chto ix net .
__________________
Free your mind and your OS will follow
|
|
|
|
|
All times are GMT. The time now is 21:46. |
|
|
![[ Xelgen ]'s Avatar](images/avatars/avatar40.gif){kind=avatar}
