[es] - Koji alogoritam za ovaj zadatak?

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 132
87.250.102.*

Profil

^{14.05.2008. u 01:08}

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.

^{14.05.2008. u 01:08}

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Moderator
Član broj: 15993
Poruke: 292
212.200.249.*

Profil

Re: Koji alogoritam za ovaj zadatak?

^{14.05.2008. u 14:38}

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.

^{14.05.2008. u 14:38}

jablan
Mladen Jablanović
Beograd

Član broj: 8286
Poruke: 3086
*.adsl-1.sezampro.yu.

Sajt: blog.radioni.ca

Profil

Re: Koji alogoritam za ovaj zadatak?

^{14.05.2008. u 15:13}

Dobre su sve one kojima treba taj isti minimalni broj dodatih slova.

_{Probajte Ruby}

^{14.05.2008. u 15:13}

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 132
87.250.102.*

Profil

Re: Koji alogoritam za ovaj zadatak?

^{14.05.2008. u 15:32}

Hvala na odgovoru, sad cu procitati link koj smi dao pa ako opet zapnem pisacu :D

^{14.05.2008. u 15:32}

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Moderator
Član broj: 15993
Poruke: 292
212.200.249.*

Profil

Re: Koji alogoritam za ovaj zadatak?

^{14.05.2008. u 15:33}

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

^{14.05.2008. u 15:33}

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 132
87.250.102.*

Profil

Re: Koji alogoritam za ovaj zadatak?

^{14.05.2008. u 17:48}

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

^{14.05.2008. u 17:48}

Nemanja_666
Nemanja Tatic
Gradiska

Član broj: 116292
Poruke: 132
87.250.102.*

Profil

Re: Koji alogoritam za ovaj zadatak?

^{15.05.2008. u 22:14}

Uradio sam zadatak. Trebao je samo naci Lcs(http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) i oduzeti duzinu rijeci sa Lcs-om.

^{15.05.2008. u 22:14}