[es] - Iterativni „podeli pa vladaj“

Mali Misha
Mihajlo Anđelković
NBGD

Član broj: 79396
Poruke: 379
78.90.101.*

ICQ: 195487525
Sajt: cpptea.com

+1 Profil

Iterativni „podeli pa vladaj“

^{05.01.2008. u 07:16 - pre 198 meseci}

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? :)

Ipak se ++uje.

Odgovor na temu

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
212.200.249.*

+1 Profil

Re: Iterativni „podeli pa vladaj“

^{08.01.2008. u 13:39 - pre 198 meseci}

Koliko sam ja shvatio u pitanju je iterativno resavanje datog problema sa osvrtom na
Divide and conquer algoritam

Posto je kod ovog algoritma (ja bih rekao cak i principa resavanja problema) sustina da se posao podeli
na manje jedinice koje su sustinski lakse za resavanje - kod samog algoritma rekurzivno deljenje do
trivijalnog problema, a u pitanju je prelazak sa rekurzivnog na iterativni princip onda bi se stvar mogla
posmatrati ovako:

suma niza brojeva = suma leve polovine niza + suma desne polovine niza (rekurzija)
suma dva broja = prvi + drugi (terminalni uslov)

gde se prilikom prelaska na iterativni metod dobija sledeci algoritam

Code:

dok broj elemenata niza > 1 {

  for i = broj elemenata niza
    novi niz [i] = stari niz [i*2] + stari niz [i*2 + 1] | stari niz [i*2]
      // u zavisnosti da li je paran ili neparan broj elemenata kod poslednjeg elementa ...

  stari niz = novi niz

}

Sto predstavlja ono sto je navedeno u prvom postu.

Drvo po sirini spram drvo po dubini :)

Najnormalnije bi bilo naravno

Code:

  sum = 0
  for i = 0 to KrajNiza -1
    sum += niz[i];

ali to naravno nije poenta ovog posta :)

Odgovor na temu