Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Koji alogoritam za ovaj zadatak?

[es] :: Art of Programming :: Koji alogoritam za ovaj zadatak?

[ Pregleda: 3986 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 221
87.250.102.*



+19 Profil

icon Koji alogoritam za ovaj zadatak?14.05.2008. u 01:08 - pre 193 meseci
Molio bih ako neko zna da mi kaze kakav alogoritam moram koristiti za ovakav tip zadatka: http://www.bhoi.net/bhoi2007/zadaci/egipat.pdf

Ne trazim resenje nego samo neki link sta bi mi pojasnilo.

I da ovo je resenje koje bas ne svatam http://www.bhoi.net/bhoi2007/zadaci/egipat.cpp pa mi ne pomaze puno, ali ako ima neko ko mi moze pojasniti bio bih mu zahvalan.
 
Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*



+1 Profil

icon Re: Koji alogoritam za ovaj zadatak?14.05.2008. u 14:38 - pre 193 meseci
Mislim da bi ti pomoglo da pogledash sledece:

http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Edit/

U pitanju je odredjivanje "distance" izmedju dva stringa ...

U konkretnom zadatku je dosta uprosceno posto nemas operatore brisanja i zamene slova sa svojim "tezinama" (ili cenom, zavisi kako
se posmatra) vec samo dodavanja, ali je sa druge strane malo zakomplikovano zato sto nemas definisanu drugu rec
vec pokusavas da je odredish tako da bude palindrom.

Znaci pogledaj (google search :D ), distancu dve rechi, dinamicko programiranje i naravno algoritam za kombinacije (to ti treba
da bi kombinovao ulazne nizove).

Moram dodati da zadatak (po mom misljenju, mada ga nisam precizno procitao) nije do kraja definisan. Nema precizne granice
sta je dovoljno dobra kombinacija - gde je granica dobre u odnosu na loshu kombinaciju - broj dodatih slova do postizanja palindroma.
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+710 Profil

icon Re: Koji alogoritam za ovaj zadatak?14.05.2008. u 15:13 - pre 193 meseci
Dobre su sve one kojima treba taj isti minimalni broj dodatih slova.
 
Odgovor na temu

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 221
87.250.102.*



+19 Profil

icon Re: Koji alogoritam za ovaj zadatak?14.05.2008. u 15:32 - pre 193 meseci
Hvala na odgovoru, sad cu procitati link koj smi dao pa ako opet zapnem pisacu :D
 
Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*



+1 Profil

icon Re: Koji alogoritam za ovaj zadatak?14.05.2008. u 15:33 - pre 193 meseci
Citat:
jablan: Dobre su sve one kojima treba taj isti minimalni broj dodatih slova.


U pravu si ...

Moze biti vise kombinacija koje daju isti a opet minimalan broj slova za dodavanje :D
 
Odgovor na temu

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 221
87.250.102.*



+19 Profil

icon Re: Koji alogoritam za ovaj zadatak?14.05.2008. u 17:48 - pre 193 meseci
Ni dalje ne kontam kako bi se moglo uraditi. Po oficijalnom resenju vidim da se radi preko DP-a, ali ne znam sta se radi. Tako ako neko zna nek pise kako :D
 
Odgovor na temu

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 221
87.250.102.*



+19 Profil

icon Re: Koji alogoritam za ovaj zadatak?15.05.2008. u 22:14 - pre 193 meseci
Uradio sam zadatak. Trebao je samo naci Lcs(http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) i oduzeti duzinu rijeci sa Lcs-om.
 
Odgovor na temu

[es] :: Art of Programming :: Koji alogoritam za ovaj zadatak?

[ Pregleda: 3986 | Odgovora: 6 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.