Deli in vladaj () predstavlja strategijo delitve problema na manjše probleme, ki so prvotnemu problemu enaki (enakega tipa). Tak postopek ponavljamo, dokler nismo sposobni rešiti podproblemov.
Strategija temelji na rekurziji.
Algoritmi
dvojiško iskanje iskanje mejnih elementov zaporedja urejanje z zlivanjem hitro urejanje () iskanje k-tega elementa po velikosti množenje števil množenje matrik Strassenovo množenje matrik Hanojski stolpi problem najbližjega para točk
Splošna procedura // a[dno], a[dno+1], ..., a[vrh]; dno>=1 so podatki procedure DeliInVladaj(a, dno, vrh, rešitev) begin if problem majhen (dno, vrh) then resi (a, dno, vrh, rešitev) else begin // problem ni majhen, potrebna delitev s := deli(dno,vrh) // index delitve, razdeli na 2 podproblema DeliInVladaj(a, dno, s, rešitev) // reši levi podproblem DeliInVladaj(a, s+1, vrh, rešitev) // reši desni podproblem Združi(dno, s, vrh, rešitev) // združi rešitve posameznega podproblema end end
Kategorija:Algoritmi