vlaiv Vladimir Vlaisavljevic Novi Sad
Član broj: 15993 Poruke: 352 212.200.249.*
|
Evo par smernica za razmisljanje:
"Backtracking" metoda:
neka je n suma
za svaki broj k manji od n, odredi sabirke n-k, resenje je
k, sabirci(n-k)
Ovaj metod je nepraktican posto ce se dosta cesto ponavljati sabirci pa bi ti trebalo
da na neki nacin pratis sta je vec bilo od resenja
na primer
za n 4
k 2
daje 2, 1 1
dok k 1
daje
1, (pa moze dati 1,1,1, 2,1, 1,2)
znaci
1,2,1
1,1,2
je isto sto i 2,1,1
sto je totalno neefikasno
drugi metod je "dinamickim" programiranjem
zamisli da za n imas ovako:
1,1,1,1,1,.....,1 (n komada)
i da postavljas u prvom koraku n-1, u drugom n-2 u trecem n-3 sibica izmedju jedinica
naprimer n =4
1|1|1|1 (to je jedini nacin da postavis n-1 odnosno 3 sibice) znaci sabirci su 1,1,1,1
pa onda imas za broj sibica n-2
1|1|1,1 = 1,1,2
1|1,1|1 = 1,2,1
1,1|1|1 = 2,1,1
U ovom slucaju iste kombinacije se pojavljuju na istom nivou broja sibica pa je lakse za pracenje.
Zapravo cak ti i ne treba da gledas "sibice" nego da gledas mesta gde sibice nedostaju. Znaci
za prvi slucaj imas da ti nedostaje 0 sibica. za drugi slucaj imas da ti nedostaje jedna sibica
i ona moze da se rasporedi na n-1 mogucih mesta znaci imas 3 mogucnosti (prvo drugo i trece).
i tako ides redom dok ne dodjes do jedne sibice koja moze na n-1 mesta da se stavi (ako pogledas ovaj
slucaj videces da se sibice simetricno rasporedjuju sa pocetka do kraja pa to uvek ostavlja mogucnost za iste sabirke
ali u suprotnom rasporedu)
1+3 = 3+1 = 1,3
Eto, nadam se da sam ti pomogao kako mozes sve razmisljati da bi resio ovaj problem.
|