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.
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.
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 ...
Č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 ;-)
Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.
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 ;-)
Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.
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)!?
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.
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.
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).
Registrovani: 5 ( sabosim, Michailbrw, morihei ueshiba, Ultrena, whitie2004 )
dinamički problem
Re: dinamički problem
Re: dinamički problem
Re: dinamički problem
Re: dinamički problem
Re: dinamički problem
Re: dinamički problem