Divide et impera (informatika)

A számitástechikában a divide et impera (Oszd meg és uralkodj) 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