dinamički problem

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?

Koliko mi se čini, to je sam niz n1 ukoliko on sam nije podniz niza n2. U suprotnom takav podniz i ne postoji.

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.

Kakve ima veze sto ima pozitivne i negativne brojeve? Ovako kako je postavljen zadatak je mnogo jednostavan jer je Mihajlovo resenje tacno.

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 ...

Potpis

CHUPCKO

Č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 ;-)

Potpis

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Aham, da li to znaci da se nizovi menjaju ili se zadatak menja ?

I dalje mi nije bas jasno, ali recimo da ok ...

Potpis

CHUPCKO

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 ;-)

Potpis

Možda se moje mišljenje promenilo, ali ne i činjenica da sam u pravu.

Aaaaaaaaaaaaaaaaaaaaaaaaaaaa

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

Cini mi se da je sve lako resiti ako imas tacnu postavku zadatka.

Potpis

CHUPCKO

Autor je ustanovio da je problem krivo postavljen :). Traži se NAJMANJI podniz niza n1 da NIJE podniz niza n1. Ispričavam se.

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)!?

I sta je bilo na kraju - da li se problem razume ili ne? ;)

Potpis

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

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!!

Najmanji podniz... zaboravio sam definiciju tacnu ali mi se cini da je najmanji podniz od jednog (dva) clana?

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.

Potpis

Njutn laze! Lake padaju brze...

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?

Aman, gde nadje [112]? Valjda si mislio [121]?

Rajko

P.S. Tebe bas tera lapsus...

Evo malo poglupo ali citiracu sam sebe da vidis da ni ja nisam rekao nista drugo,
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.

Potpis

Njutn laze! Lake padaju brze...

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).