[ mipko @ 11.09.2003. 13:07 ] @
Pozdrav,

PROBLEM :

treba izgeneristai niz od N elemenata (N>= 10 000). Elementi niza su brojevi:
od 1 do 11; ukljucujuci 1 i 11. Niz treba da bude takav da bilo koji proizvoljno uzeti PODNIZ elemenata ima sumu =< 18, ili >= 22. Elementi se smeju ponavljati u nizu.

Izgledalo mi je jednostavno, ali...
[ leka @ 11.09.2003. 14:30 ] @
Nepisan zakon na ES-u je da ti ljudi koji mogu da pomognu nece pomoci ako makar ne das neko svoje resenje problema, to uopste ne mora da bude resenje, vec nesto sto ce dokazati da si se bar malo pomucio oko resavanja, a ne da si dobio zadak i onda brze-bolje dosao na ES misleci "e sada ce meni neki bezveznjak, koji nista drugo ne zna osim da sedi za racunarom i kodira, resiti ovaj zadatak za par minuta"...
[ mipko @ 11.09.2003. 15:31 ] @
nemam resenje, nisam se ni pomucio
ajde nek mi neko servira :)
[ filmil @ 11.09.2003. 20:35 ] @
Citat:
mipko:Niz treba da bude takav da bilo koji proizvoljno uzeti PODNIZ elemenata ima sumu =< 18, ili >= 22.


(11, 11, 11, ...)

... ili nam ti zapravo nisi rekao kako tačno glasi zadatak? Da li je ovo još jedan primerak dinamičkog problema?

f
[ mipko @ 11.09.2003. 20:59 ] @
Ma problem mi je delova jako jednostavno dok nisam seo da pokusam da ga resim.

Evo malo detaljnijeg objasnjenja

ogranicimo se na niz of 5 elemenata :

1 7 9 8 6, koji god podniz iz njega uzeli :

[1], [7], [9], [8]. [6], [1,7], [7,9], [9,8], [8, 6],
[1,7,9] [7,9,8] [9, 8, 6] [1 , 7, 9 ,8] [7, 9, 8, 6]

ce zadovoljiti zadati uslove:
1. da je suma elemenata podniza manja ili jednaka od 18
2. -------------||----------- podniza veca ili jednaka od 22

sad zamislite da trebate da napravite niz od SVIH 11 elemenata (brojevi od 1 do 11) i to takav da mu bilo koji podniz zadovolji oba uslova. Taj VELIKI niz treba zaista da bude veliki (10 000 > elemenata) uopste nije bitno da li ce se nakon nekog vremena elementi niza poceti da ponavljaju u nekom paternu. Bitno mi je samo da ako prepolovim taj VELIKI niz budem 100% da oba manja niza zadovoljavaju zadati uslov.

Nemojte misliti da sam lenstina koja ceka odgovor. Radim na resenju, ali mi ne ide...
[ Shipa @ 11.09.2003. 23:48 ] @
Citat:
mipko:
Ma problem mi je delova jako jednostavno dok nisam seo da pokusam da ga resim.

Evo malo detaljnijeg objasnjenja

ogranicimo se na niz of 5 elemenata :

1 7 9 8 6, koji god podniz iz njega uzeli :

[1], [7], [9], [8]. [6], [1,7], [7,9], [9,8], [8, 6],
[1,7,9] [7,9,8] [9, 8, 6] [1 , 7, 9 ,8] [7, 9, 8, 6]

ce zadovoljiti zadati uslove:
1. da je suma elemenata podniza manja ili jednaka od 18
2. -------------||----------- podniza veca ili jednaka od 22

sad zamislite da trebate da napravite niz od SVIH 11 elemenata (brojevi od 1 do 11) i to takav da mu bilo koji podniz zadovolji oba uslova. Taj VELIKI niz treba zaista da bude veliki (10 000 > elemenata) uopste nije bitno da li ce se nakon nekog vremena elementi niza poceti da ponavljaju u nekom paternu. Bitno mi je samo da ako prepolovim taj VELIKI niz budem 100% da oba manja niza zadovoljavaju zadati uslov.

Nemojte misliti da sam lenstina koja ceka odgovor. Radim na resenju, ali mi ne ide...


11,11,1,11,11,2,11,11,3,11,11,4,11,11,5,11,11,6,11,11,7,11,11,3,8,3,11,11,2,9,2,11,11,1,10,1,11,11

ako ti treba vise brojeva od ovoga, samo pusti sve jedanaestice do kraja

verovatno moze i krace ali rekao si da mogu da se ponavljaju elementi... a ti sad vidi kako sam dosao do ovoga :)

[ filmil @ 11.09.2003. 23:58 ] @
Citat:
mipko:
Evo malo detaljnijeg objasnjenja
[ ... ]
Bitno mi je samo da ako prepolovim taj VELIKI niz budem 100% da oba manja niza zadovoljavaju zadati uslov.


Mipko, nisi baš dobro definisao problem, čini mi se da ima koliko god hoćeš takvih različitih nizova, a ovaj uslov sa polovljenjem ti baš i nije neki, jer ako veliki niz ispunjava uslov, i manji automatski ispunjavaju, pošto je svaki podniz manjih ujedno i podniz velikog niza.

Mislim da ti je najbolji izlaz da lepo uzmeš i ručno iskonstruišeš niz koji ti treba, mada mi nije baš jasno šta bi neko onda mogao da radi sa tim. Drugo je pitanje generisanje SVIH takvih nizova ili brojanje koliko datih nizova može biti, ali koliko vidim to nije problem kog si postavio. Tako reći ostaje mi misterija šta si zapravo hteo. Izvinjavam se ako sam prevideo nešto očigledno.

f


[ mipko @ 12.09.2003. 09:48 ] @

10 000 elemenata. pri tom niz 999999999999...9 i takvi nizovi nisu resenje.
meni ne trebaju svi nizovi koji zadovoljavaju postavljene uslove. dovoljan mi je jedan.

probaj da napises niz od sto elemenata a da upotrebis sve elemente (1..11).

[ filmil @ 12.09.2003. 09:51 ] @
Šta tačno fali ovom Shipinom rešenju gore?

Najpre si tražio rešenje i dobio si jedno, doduše trivijalno. Zatim si tražio rešenje u kome se pojavljuju svi brojevi od 1 do 11 i to si rešenje dobio. Ali kako vidim nisi ni jednim ni drugim zadovoljan.

S obzirom da mi se prilično čini da smo u oba slučaja ispunili (tada važeće) zahteve a da i dalje nije odgovor na tvoje pitanje, moraću opet da te zamolim da dobro razmisliš i potom dobro objasniš šta želiš da dobiješ i zašto.

Koje osobine treba da ima niz? Dosad smo ustanovili da:

- u njemu moraju da se pojave brojevi 1..11 bar jednom.
- svaki podniz ima zbir različit od 19,20 i 21.
- prva i druga polovina niza ispunjavaju iste uslove.

Da bi ispunio oba uslova dužina niza treba da bude parna jer inače nemaš dve polovine. Uzmeš prvih 5000 elemenata Shipinog niza i zatim ih iskopiraš počev od 5001 elementa dalje i definitivno dobijaš niz od 10.000 elemenata koji ispunjava gore navedene uslove.

Primeti da ako dozvoliš proizvoljnu podelu niza, onda tvoj zadatak nema rešenja jer uvek mogu da podelim na dva tako što u jedan stavim 10 početnih elemenata a u drugi sve ostale. Ovaj niz od 10 početnih elemenata nikako ne može ispuniti uslov da se u njemu pojavlje svih 11 brojeva. Kao što vidiš nešto mi u tvojoj postavci nikako ne štima.

f
[ mipko @ 12.09.2003. 13:26 ] @
raspodela


Citat:
filmil:
Šta tačno fali ovom Shipinom rešenju gore?

[ srki @ 12.09.2003. 13:49 ] @
Reci koji je to uslov za raaposelu? Ako neces da se neki broj ponavlja do kraja onda mozes ceo taj niz da ponavljas umesto jedanaestica na kraju.

Dato ti je resenje koje zadovoljava tvoje uslove. Ako mislis da neki uslov ne zadovoljava napisi tacno koji uslov.
[ filmil @ 12.09.2003. 13:55 ] @
Citat:
mipko:
raspodela


Moraćeš, sebe radi, da se potrudiš da dobro definišeš šta ti treba. Raspodelu evo dosad niko nije ni pominjao. Možda ti neće ni biti potreban savet kada shvatiš šta zapravo treba da rešiš.

Moraćeš, nas radi, da uložiš malo više truda u pisanje obrazloženja zašto dato rešenje ne valja uprkos tome što ispunjava tvoje specifikacije. Ovako nam udeliš jednu reč pa onda mi da se dosećamo šta si ti time mislio i da li ima smisla uopšte se truditi oko rešavanja pošto u sledećoj poruci možda ispadne da ti treba nešto sasvim deseto.

Odlučio sam da sačekam da postavka problema iskonvergira pa ću se onda uključiti nazad u priču.

f
[ Gojko Vujovic @ 12.09.2003. 14:03 ] @
Leka kaže da je nepisano pravilo, ali ja tvrdim da je odavno napisano.

Pogledajte deo "Uputstvo o tome kako ne treba koristiti ES forum", pravilo 2. na sledećoj adresi koja je linkovana sa svake stranice ovog foruma: http://www.elitesecurity.org/about/rules.pdf
[ mipko @ 12.09.2003. 16:35 ] @
hvala svima na trudu, da mi pomognu.

Resio sam problem i uploadovacu kompletno resenje u ponedeljak.

Kao sto rekoh nisam parazit ;-)

Citat:
Gojko Vujovic:
Leka kaže da je nepisano pravilo, ali ja tvrdim da je odavno napisano.

Pogledajte deo "Uputstvo o tome kako ne treba koristiti ES forum", pravilo 2. na sledećoj adresi koja je linkovana sa svake stranice ovog foruma: http://www.elitesecurity.org/about/rules.pdf

[ mipko @ 12.09.2003. 16:38 ] @
Nema vise potrebe, hvala ti na trudu.

znas kako kaze Chesterton ?

"It's not that they can't find sollution - ut's they don't see the problem" ;-)



Citat:
filmil:
Citat:
mipko:
raspodela


Odlučio sam da sačekam da postavka problema iskonvergira pa ću se onda uključiti nazad u priču.

f