[ djoka_kokos @ 19.10.2017. 14:32 ] @
Pretpostavimo da imamo kvadar zapremine V = 2 dm^3. Koliko kombinacija celobrojnih stranica postoji, ako ni jedna stranica nije manja od 5cm, ni veća od 25cm ( Dakle, stranice mogu da imaju vrednosti 5 i 25, ali ne manje od 5 i ne više od 25 ) ?

S obzirom da su u pitanju celobrojne dužine stranica, svestan sam da nema puno rešenja, ali ne mogu da nađem način da uradim ovo a da nije "babski" ( nabrajanje ).

Da li postoj neki postupak kojim bi ovo moglo da se uradi ili se nabrajanjem navode sva rešenja, pa se onda dokazuje i objašnjava zašto ostala rešenja nemaju smisla ?

Hvala :)

[Ovu poruku je menjao djoka_kokos dana 19.10.2017. u 16:07 GMT+1]
[ Shadowed @ 19.10.2017. 16:05 ] @
Fali ti podatak - sta taj ceo broj oznacava. Da li centimetre ili neke druge jedinice. Od toga zavisi broj resenja.
[ djoka_l @ 19.10.2017. 16:43 ] @
uz pretpostavku da celobrojna stranica znači da je dužina stranice ceo broj CENTIMETARA, tada 2dm3 predstavlja 2000cm3

Nađeš sve faktore broja 2000, a to su {1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 125, 200, 250, 400, 500, 1000, 2000}
Zbog ograničenja da stranice mogu biti samo između 5 i 25 ostaje ti {5, 8, 10, 16, 20, 25}
Rešenja su:
{5, 16, 25}
{5, 20, 20}
{8, 10, 25}
Znači, ukupno 3 rešenja, ako dozvoliš i permutacije, onda 15 (prvo i treće rešenje ima 6 permutacija, a drugo samo 3 zbog ponavljanja broja 20)

Kada se traži celobrojno rešenje nekog problema, onda je to kombinatorni problem.

Ups, postoji i rešenje {10,10,20}, dakle 4 različita rešenja, ili 18 ako računamo i permutacije

Code (python):


product = 2000
low = 5
high = 25

for x in range (low, high+1):
    for y in range (x, min(high, product/x )+1):
        for z in range (y, min(high, product/(x*y))+1):
            if x*y*z == product:
                print x,y,z

$python main.py
5 16 25
5 20 20
8 10 25
10 10 20
 



[Ovu poruku je menjao djoka_l dana 19.10.2017. u 18:12 GMT+1]
[ djoka_kokos @ 19.10.2017. 18:45 ] @
Citat:
uz pretpostavku da celobrojna stranica znači da je dužina stranice ceo broj CENTIMETARA, tada 2dm3 predstavlja 2000cm3

Nađeš sve faktore broja 2000, a to su {1, 2, 4, 5, 8, 10, 16, 20, 25, 40, 50, 80, 100, 125, 200, 250, 400, 500, 1000, 2000}
Zbog ograničenja da stranice mogu biti samo između 5 i 25 ostaje ti {5, 8, 10, 16, 20, 25}
Rešenja su:
{5, 16, 25}
{5, 20, 20}
{8, 10, 25}
Znači, ukupno 3 rešenja, ako dozvoliš i permutacije, onda 15 (prvo i treće rešenje ima 6 permutacija, a drugo samo 3 zbog ponavljanja broja 20)

Kada se traži celobrojno rešenje nekog problema, onda je to kombinatorni problem.

Ups, postoji i rešenje {10,10,20}, dakle 4 različita rešenja, ili 18 ako računamo i permutacije

Code:
Code (python):


product = 2000
low = 5
high = 25

for x in range (low, high+1):
    for y in range (x, min(high, product/x )+1):
        for z in range (y, min(high, product/(x*y))+1):
            if x*y*z == product:
                print x,y,z

$python main.py
5 16 25
5 20 20
8 10 25
10 10 20


Hvala, đoko, imenjače :D

Našao sam ja sve faktore, uvideo taj interval i ispisao 4 moguća rešenja.(Nije potrebno permutovati stranice.)

Ali, mene nešto drugo muči... vi ste koristili kombinatoriku da posle nađene 4 kombinacije vidite kako one permutuju i to je okej, ali mene interesuje da li postoji način da se ovaj zadatak reši kombinatorikom odmah, znači da odmah dobijem koliko rešenja ima, čak i bez potrebe da znam koja su ? Ili neki drugi način, bilo šta :/

Inače, hvala svejedno :) , Na vašem postu nije postojala opcija "odgovori citatom", ili je bar ja nisam video, tako da sam ručno ovo, valjda će ličiti na našto.

@Shadowed, uzimaju se u obzir centimetri, kao što je djoka_l uradio. Nisam napomenuo, izvinjavam se.
[ djoka_l @ 19.10.2017. 19:35 ] @
Ne može da se citira poruka koja je prva iznad odgovora.
[ djoka_kokos @ 19.10.2017. 19:37 ] @
Aha, pa logicno. A sto se tice zadatka? Postoji li nekie drugi nacin ili ne? Izvinjavam se sto sam dosadan, ali stvarno me nervira :)
[ djoka_l @ 19.10.2017. 20:05 ] @
Ne znam za konkretan problem, ali mi on liči na probleme particionisanja skupa prirodnih brojeva, ili neku njihovu varijantu. Ovi problemi ne da nemaju analitičko rešenje, većina njihovih varijanti su NP kompletni, znači, u opštem slučaju nisu čak ni izračunljivi.

Problem koji sam rešio je polinomijalni, ali mislim da nema prečice...
[ djoka_kokos @ 19.10.2017. 20:45 ] @
Okej, hvala Vam puno. :)