[es] - dinamički problem

Bijeli_dedA
Jurica Cerovec
Zagreb

Član broj: 10238
Poruke: 9
*.cmu.carnet.hr

Profil

^{23.06.2003. u 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?

^{23.06.2003. u 00:01}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

Profil

Re: dinamički problem

^{23.06.2003. u 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.

^{23.06.2003. u 05:17}

Reljam
Relja Markovic
Project Natal - Microsoft Game Studios
Seattle, WA

Član broj: 531
Poruke: 1739
*.client.attbi.com

Sajt: www.linkedin.com/in/relja..

Profil

Re: dinamički problem

^{23.06.2003. u 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.

^{23.06.2003. u 09:10}

srki
Srdjan Mitrovic
Auckland, N.Z.

Član broj: 2237
Poruke: 3643
*.ihug.net

Profil

Re: dinamički problem

^{23.06.2003. u 14:03}

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

^{23.06.2003. u 14:03}

Mihailo Kolundzija
Novi Sad

Član broj: 11323
Poruke: 100
*.ftn.ns.ac.yu

Profil

Re: dinamički problem

^{23.06.2003. u 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.

^{23.06.2003. u 18:07}

chupcko
Beograd

Član broj: 5560
Poruke: 1104
*.verat.net

Sajt: www.google.com

Profil

Re: dinamički problem

^{24.06.2003. u 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 ...

CHUPCKO

^{24.06.2003. u 10:09}

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beograd-3.tehnicom.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

Profil

Re: dinamički problem

^{24.06.2003. u 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 ;-)

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

^{24.06.2003. u 11:44}

chupcko
Beograd

Član broj: 5560
Poruke: 1104
*.verat.net

Sajt: www.google.com

Profil

Re: dinamički problem

^{24.06.2003. u 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 ...

CHUPCKO

^{24.06.2003. u 12:23}

tOwk
Danilo Šegan
Zemun/Beograd

Član broj: 94
Poruke: 2743
*.beograd-3.tehnicom.net

ICQ: 9344053
Sajt: alas.matf.bg.ac.yu/~mm011..

Profil

Re: dinamički problem

^{24.06.2003. u 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 ;-)

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

^{24.06.2003. u 12:59}

chupcko
Beograd

Član broj: 5560
Poruke: 1104
*.verat.net

Sajt: www.google.com

Profil

Re: dinamički problem

^{24.06.2003. u 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.

CHUPCKO

^{24.06.2003. u 15:03}

Bijeli_dedA
Jurica Cerovec
Zagreb

Član broj: 10238
Poruke: 9
*.cmu.carnet.hr

Profil

Re: dinamički problem

^{01.07.2003. u 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.

^{01.07.2003. u 17:20}

lucky

Član broj: 2032
Poruke: 56
*.matf.bg.ac.yu

Jabber: lucky@elitesecurity.org

Profil

Re: dinamički problem

^{02.07.2003. u 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)!?

^{02.07.2003. u 22:35}

leka
Dejan Lekić
senior software engineer, 3Developers Ltd.
London, UK

Član broj: 234
Poruke: 2530
*.racasse.se

Sajt: dejan.lekic.org

Profil

Re: dinamički problem

^{07.07.2003. u 15:13}

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

Dejan Lekic
software engineer, MySQL/PgSQL DBA, sysadmin

^{07.07.2003. u 15:13}

Bijeli_dedA
Jurica Cerovec
Zagreb

Član broj: 10238
Poruke: 9
*.cmu.carnet.hr

Profil

Re: dinamički problem

^{08.07.2003. u 21:57}

Kvragu. ne znam 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!!

^{08.07.2003. u 21:57}

byTer

Član broj: 10936
Poruke: 1221
*.ptt.yu

ICQ: 47761626

Profil

Re: dinamički problem

^{08.07.2003. u 22:46}

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

^{08.07.2003. u 22:46}

Koljenovic
Malik Koljenovic
BiH

Član broj: 9334
Poruke: 130
*.as1.vi-1.bih.net.ba.

Profil

Re: dinamički problem

^{10.07.2003. u 21:01}

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

Njutn laze! Lake padaju brze...

^{10.07.2003. u 21:01}

Bijeli_dedA
Jurica Cerovec
Zagreb

Član broj: 10238
Poruke: 9
*.cmu.carnet.hr

Profil

Re: dinamički problem

^{10.07.2003. u 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?

^{10.07.2003. u 22:36}

Rapaic Rajko
programer, Grappolo
Bgd

Član broj: 4105
Poruke: 410
*.ppp-bg.sezampro.yu

Profil

Re: dinamički problem

^{12.07.2003. u 00:01}

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

Rajko

P.S. Tebe bas tera lapsus...

^{12.07.2003. u 00:01}

Koljenovic
Malik Koljenovic
BiH

Član broj: 9334
Poruke: 130
*.as1.vi-1.bih.net.ba.

Profil

Re: dinamički problem

^{13.07.2003. u 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.

Njutn laze! Lake padaju brze...

^{13.07.2003. u 00:13}

Bijeli_dedA
Jurica Cerovec
Zagreb

Član broj: 10238
Poruke: 9
*.cmu.carnet.hr

Profil

Re: dinamički problem

^{15.07.2003. u 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).

^{15.07.2003. u 00:18}