Divide et impera (informatika)
A számitástechikában a divide et impera (Oszd meg és uralkodj[1]) egy rekurzión alapuló programozási stratégia, amellyel egy komplex feladatot addig bontunk le részfeladatokra, amíg a részfeladatok megoldása triviális lesz. Használják különböző rendezésekhez (pl. quicksort), nagy számok szorzásánál, vagy diszkrét Fourier transzformációk számításánál.
Részletes leírás
Próbáljuk meg egy konkrét feladattal leírni a divide et impera módszer metodikáját. Tegyük fel, hogy meg kell találnunk egy tömb legnagyobb elemét. Ehhez a legegyszerűbb megoldás az lenne, hogy összehasonlítjuk az első és a második elemet, s amelyik a kettő közül nagyobb, az lesz az ideiglenes maximumunk. Aztán ezt az ideiglenes maximumot hasonlítjuk a tömb többi eleméhez, s természetesen cseréljük, ha találunk nagyobb elemet.
Ha divide et impera módszerrel szeretnénk megoldani, akkor azzal kezdjük a feladatot, hogy felosztjuk a tömböt két egyforma részre, mindkettőnek megkeressük a maximumát, s csak ezt a két maximumot hasonlítjuk össze. Igen ám, de a két féltömböt is feloszthatjuk még két féltömbre (vagyis lesz négy negyedtömbünk) rekurzívan, s ezt egészen addig ismételhetjük, amíg egy tömbrészletben csak egy elem lesz, vagyis triviális lesz, hogy az a maximum. Az alábbi egyszerű C++ programban láthatjuk ennek az implementációját.
#include <iostream> #include <stdlib.h> #define n 10000 using namespace std; int v[n]; /* Divide et Impera módszeren alapuló maximum kereső függvény, megkeresi a maximumot a tömbben az argumentumként megadott két index között */ int max(int i, int j) { int max1, max2, kozep; //ha a két index egyezik, //akkor már nem lehet tovább bontani a tömböt, //tehát ez az érték lesz a maximum if (i==j) return v[i]; else { //ha nem, akkor keresd meg a maximumot a kapott //tömb jobb és bal felén s térítsd vissza a nagyobb értéket kozep = (i+j)/2; max1 = max(i, kozep); max2 = max(kozep+1, j); return max1>max2?max1:max2; } } int main( ) { //feltölti véletlenszámokkal a tömböt srand(0); for (int i=0; i<n; i++) { v[i]=rand(); } //számítsd ki a maximumot //a megadott két index között int maximum = max(0,n); cout<<"max="<<maximum; return 0; }
Ha minimumkeresésre szeretnénk egy divide et impera algoritmust kidolgozni, akkor csak ezt a sort kellene
return max1>max2?max1:max2
erre változtatni:
return max1<max2?max1:max2
Források
- ↑ Kátai Zoltán, Algoritmusok felülnézetből (Scientia Kiadó, Kolozsvár, 2007).