[ Bijeli_dedA @ 23.06.2003. 00:01 ] @
Zadatak glasi ovako. Treba naći najveći podniz niza n1 da nije podniz niza n2. Znam da to treba rješavati dinamički, ali ne kužim kako. Ideje?
[ Mihailo Kolundzija @ 23.06.2003. 05:17 ] @
Koliko mi se čini, to je sam niz n1 ukoliko on sam nije podniz niza n2. U suprotnom takav podniz i ne postoji.
[ Reljam @ 23.06.2003. 09:10 ] @
Zadatak podrazumeva da niz ima i pozitivne i negativne brojeve. Nazalost, ne znam kako bi ga resio primenom dinamickog programiranja, ali postoji 'obicno' resenje, i to u linearnom vremenu.
[ srki @ 23.06.2003. 14:03 ] @
Kakve ima veze sto ima pozitivne i negativne brojeve? Ovako kako je postavljen zadatak je mnogo jednostavan jer je Mihajlovo resenje tacno.
[ Mihailo Kolundzija @ 23.06.2003. 18:07 ] @
Ako je ono što sam napisao tačno (a čini mi se da jeste), zadatak se svodi na proveru da li je n1 podniz niza n2. To se može uraditi jednim prolaskom kroz n2, a može i dinamičkim programiranjem (zašto lako kad može i komplikovano) - odredi se najveći zajednički podniz od n1 i n2 i proveri se da li mu je dužina jednaka sa n1.
[ chupcko @ 24.06.2003. 10:09 ] @
Jel moze za nas manje upucene da se tacno kaze sta je to "dinamicki problem" ?
Mislim ne shvatam u cemu je problem sa ovim zadatkom, mozda od sume ne vidim drvo, a mozda se u medjuvremenu pojavile nove paradigme: krljusno programiranje, trtmrt programiranje, objektno ...
[ tOwk @ 24.06.2003. 11:44 ] @
Čupko, situacija je veoma jednostavna: dinamički problem je onaj koji se menja kako prolazi vreme.

Znači, na početku je data jedna „specifikacija“ problema, a kako vreme odmiče to će se ona menjati, i stara rešenja neće valjati. Zato, sada očekujemo da se izmeni problem, pa da vidimo gde su greške ;-)
[ chupcko @ 24.06.2003. 12:23 ] @
Aham, da li to znaci da se nizovi menjaju ili se zadatak menja ?

I dalje mi nije bas jasno, ali recimo da ok ...
[ tOwk @ 24.06.2003. 12:59 ] @
Neee, nisi razumeo — „dinamički problem“ je onaj koji danas glasi: „naći četvrti prost broj“, sutra će glasiti „naći prost broj veći od četiri“, a prekosutra „naći četiri broja veća od četiri od kojih su svaka dva uzajamno prosta“. :-)

Tj. problem najverovatnije nije ispravno postavljen, pa će se menjati kada autor uvidi da je tako ;-)
[ chupcko @ 24.06.2003. 15:03 ] @
Aaaaaaaaaaaaaaaaaaaaaaaaaaaa

Pa da, a ja se ponadao neka nova metodologija programiranja :))).

Cini mi se da je sve lako resiti ako imas tacnu postavku zadatka.
[ Bijeli_dedA @ 01.07.2003. 17:20 ] @
Autor je ustanovio da je problem krivo postavljen :). Traži se NAJMANJI podniz niza n1 da NIJE podniz niza n1. Ispričavam se.
[ lucky @ 02.07.2003. 22:35 ] @
Izgleda da je problem opet krivo postavljen, ako se ne varam?
Pretpostavaljam da je u pitanju najmanji podniz niza N1 koji nije podniz
niza N2 (posto bi ovako to bio prazan skup)!?
[ leka @ 07.07.2003. 15:13 ] @
I sta je bilo na kraju - da li se problem razume ili ne? ;)
[ Bijeli_dedA @ 08.07.2003. 21:57 ] @
Kvragu. Neznam pisati, razmišljati, ne služe me ruke.. ma ne služi me ni mozak! Drugi niz je N2 kako je rekao i lucky. Nemogu vjerovati!!
[ byTer @ 08.07.2003. 22:46 ] @
Najmanji podniz... zaboravio sam definiciju tacnu ali mi se cini da je najmanji podniz od jednog (dva) clana?
[ Koljenovic @ 10.07.2003. 21:01 ] @
Neznamo ni kako glasi zadatak a da znamo kako da ga rijesimo, to je neka nova metoda? :) Salim se, najmanji podniz moze da se sastoji od minimum 2 broja, jer ako to nisu dva clana onda to nije najmanji niz nego najmanji clan jer ako je niz npr. 45367288124 onda je namanji (i najkraci!) podniz 12 a ako se trazi najduzi (i najmanji) onda je to druga prica (nemogu ovako izracunati u glavi). Otprilike to je to za najmanjni podniz e onda kada nadjes najmanji podniz onda provjeravas dali on postoji u n2, ako postoji onda trazis slijedeci ako ne to je taj trazeni.
[ Bijeli_dedA @ 10.07.2003. 22:36 ] @
Nemora biti tako. Gledaj, recimo:
n1 = [1,2,1,2,1]
n2 = [2,1,2,2,1]

Rješenje nemože biti dvočlano, tj. nemože biti niti [1,2] niti [2,1] nego je
r = [1,1,2]

Ok?
[ Rapaic Rajko @ 12.07.2003. 00:01 ] @
Aman, gde nadje [112]? Valjda si mislio [121]?

Rajko

P.S. Tebe bas tera lapsus...
[ Koljenovic @ 13.07.2003. 00:13 ] @
Evo malo poglupo ali citiracu sam sebe da vidis da ni ja nisam rekao nista drugo,
Citat:
onda je namanji (i najkraci!) podniz 12
Obrati paznju na boldovani text, ja sam rekao da je to i najkraci podniz a to u tebe je mislim najmanji i najduzi. Prema tome ja mislim da nisam pogrijesio bas zato sam naglasio ono najmani i najveci, ako neko misli da jos uvjek grijesim bilo bi mi drago da cujem ispravku.
[ Bijeli_dedA @ 15.07.2003. 00:18 ] @
Oprosti, nisam čitao glavom, nego samo očima. Ono šo si napisao i je i nije točno. Najmanji podniz može biti i jedan član, ali može biti i cijeli taj niz. Nebi bilo teško rješiti zadatak za nizove s malim brojem članova (samo brute force i to bi radilo), nego za nizove od npr. 1000 članova. Zato sam i napisao da bi rješavao dinamički i zato tražim savjet od vas.

A šta se tiče onog primjera, pogledaj i sam da je moj dobar. [1,2,1] JE podniz drugog, a [1,1,2] NIJE (vidi ispravku ispravka zadatka :) koju je napisao Lucky).
[ chupcko @ 15.07.2003. 10:20 ] @
Uf, zanimljivo je ovo dinamicko programiranje, Danilo je bio u pravu, kada nije definisan problem do kraja zna da bude bas zanimljivo :)

Dakle jel mozete za nas sa jeftinijim ulaznicama da ponovite zadatak, ali ovog puta ispravno sa jednim ili bar dva priemra, naravno ako moze, sto metoda grube sile ne bi bila dobra ???
[ Rapaic Rajko @ 15.07.2003. 11:42 ] @
Citat:
Bijeli_dedA:
A šta se tiče onog primjera, pogledaj i sam da je moj dobar. [1,2,1] JE podniz drugog, a [1,1,2] NIJE (vidi ispravku ispravka zadatka :) koju je napisao Lucky).


Da li je u onom primeru n1 PRVI niz, a n2 DRUGI niz? Ako jeste, onda samo jos jedno pitanje: da li ti nas ovde zavitlavas?

Rajko
[ Mihailo Kolundzija @ 15.07.2003. 13:01 ] @
Rajko, u pitanju je podniz, a njegovi elementi ne moraju biti uzastopni clanovi odgovarajuceg niza. Uostalom, pogledaj pod Subsequences:
http://www.maths.lse.ac.uk/Courses/MA203/sec1a.pdf

A sto se resenja tice, ne vidim kako bi se moglo naci "dinamicki" - pre ce biti da je gruba sila u pitanju.
[ Rapaic Rajko @ 16.07.2003. 11:51 ] @
Deda, moje izvinjenje. Imao sam pogresnu predstavu o tome sta se smatra podnizom datog niza...sorry.
Nesto o samom problemu. Backtracking...i jeste i nije primena grube sile. Jeste, zato sto, u principu, isprobavas moguce kombinacije; nije, zato sto uvodis neke uslove koji skracuju moguce "staze" ili odbacuju citave "grane" u trazenju pravog resenja. Stos je, jasno, u tim uslovima, i mislim da se to ovde moze iskoristiti.
Pozdrav

Rajko
[ Koljenovic @ 16.07.2003. 20:14 ] @
Brute-Force ne dolazi u obzir osim kao poslijednja opcija, a ja mislim da jedan broj ne moze biti podniz nego je on samo clan niza, ne znam mozda nisam u pravu :|. A evo ovako da ja sad nebih prekucavao rjesenja evo ti link ka knjizi Dinamickog programiranja (na srpskom, Milana Vugdelije) u kojoj ces naci objasnjenje i algoritam za slican problem, to je Najduzi zajednicki podniz ali ako ga malo editujes smozes dobiti ono sto trazis, jer ti bi trebao to najbolje da znas, da mi nebi morali da odgonetavamo sto si ti mislio reci u objasnjenju zadatka najbolje je da ti to sam uradis. Pa evo link (mogao si koristiti pretrazivanje):

http://www.devbase.net/knjige/Dinamicko%20programiranje.pdf
[ Bijeli_dedA @ 16.07.2003. 23:42 ] @
Cujte, taj zadatak je s hrvatskog državnog takmičenja i izgubio sam 4 sata na njemu da ga riješim, naravno bezuspješno. Zato sam vas i molio za pomoć iako mi nije baš dobro krenulo s svim tim lapsusima. 100% sam uvjeren da za nizove od po 1000 članova samo dinamičko programiranje može dati odgovor u roku od 5 sekundi, zato otpada i backtracking i brute-force i ne znam koje još metode.
Puno hvala na knjizi, možda mi bude sad lakše odgonetnuti rješenje.
[ Koljenovic @ 17.07.2003. 19:30 ] @
Nema na cemu. Samo jel imas ti sajt sa tim zadacima i stranicu hrvatskog tima koji priprema takmicenja?
[ Bijeli_dedA @ 18.07.2003. 00:03 ] @
Tim nema stranicu (koliko znam), ali na službenoj stranici saveza public.srce.hr/hsin imaš te a i hrpu starih zadataka. Uživaj.
[ Koljenovic @ 18.07.2003. 22:43 ] @
Hvala na linku.