[ Mali Misha @ 05.01.2008. 07:16 ] @
Ovo mi je blaga dilema, ali ipak želim da se osiguram da nema boljih ili tačnijih rešenja. Dakle rekurzivni „podeli pa vladaj“ algoritam prvo podeli problem (recimo niz) na dva dela. Onda svakog od njih šalje samom sebi na dalje deljenje, i tako u rekurzivno dok se ne dođe do dovoljno malih atoma problema da bi se mogli rešiti. Onda se oni rešavaju i zavisno od tipa problema se izabira jedno rešenje ili se rešenja vraćaju rekurzivno unazad da bi se od njih napravilo rešenje. E sad, kod iterativnog rešenja ono što radim nije eksplicitno deljenje, već polazim od pretpostavke da je sve već podeljeno i sklapam ga u veću celinu. Evo, daću primer sa jednim nizom, npr. 1,2,3,4,5,6,7,8,9 čiju sumu elemenata treba izračunati. Na početku postoji samo ovaj niz, Code: 1 2 3 4 5 6 7 8 9 Pretposavljam da je podela već napravljena tj. da u iterativnoj verziji treba napraviti korak koji bi se inače napravio tek nakon što rekurzija dostigne svoj vrhunac. Sabiram sve susedne elemente: Code: 1 2 3 4 5 6 7 8 9 \/ \/ \/ \/ / 3 7 11 15 9 Ovako dobijam novi niz na kome postupak treba ponoviti. I tako u krug, dok se ne dođe do samo jednog broja: Code: 1 2 3 4 5 6 7 8 9 \/ \/ \/ \/ / 3 7 11 15 9 \ / \ / / 10 26 9 \ / / 36 9 \ / 45 Dakle, da li je ovo ispravan rezon za iterativni „podeli pa vladaj“? Ima li možda boljeg? :) |