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> const int n = 10000; 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) { if (i == j) { // 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 return v[i]; } else { // ha nem, akkor keresd meg a maximumot a kapott // tömb jobb és bal felén s add vissza a nagyobb értéket int kozep = (i + j) / 2; int max1 = max(i, kozep); int 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); std::cout << "max = " << maximum << std::endl; }
Források
- ↑ Kátai Zoltán, Algoritmusok felülnézetből (Scientia Kiadó, Kolozsvár, 2007).