Divide et impera

Más néven: oszd meg és uralkodj!

Feladatmegoldási módszer, melyben az eredeti feladatot két (vagy több) kisebb részre bontjuk, majd ezen kisebb részek megoldásából alakítjuk ki az eredeti feladat megoldását.

Tipikusan három fázisa van:

Feladatok

1. Tömb elemeinek összege oszd meg és uralkodj módszerrel:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include <iostream>
using namespace std;

int osszeg(int t[], int start, int veg)
{
    if (start > veg) return 0;
    if (start == veg) return t[start];

    int kozep = (start + veg) / 2;

    int s1 = osszeg(t, start, kozep);
    int s2 = osszeg(t, kozep+1, veg);

    return s1 + s2;
}

2. Határozzuk meg divide et impera módszerrel, hogy egy tömbben hány olyan elem van, ami 3-nak többszöröse!

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

int tobbsz(int t[], int start, int veg)
{
    if (start > veg) return 0;
    if (start == veg) {
        if (t[start] % 3 == 0)
            return 1;
        else
            return 0;
    }

    int kozep = (start + veg) / 2;

    int db1 = tobbsz(t, start, kozep);
    int db2 = tobbsz(t, kozep+1, veg);

    return db1 + db2;
}

int main()
{
    int n = 5;
    int t[] = { 10, 2, 30, 5, 6 };

    int s = tobbsz(t, 0, n-1);

    cout << s << endl;

    return 0;
}

Házi

3. Határozzuk meg egy tömb legkisebb elemét divide et impera módszerrel.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

int minimum(int t[], int start, int veg)
{
    if (start == veg) return t[start];

    int kozep = (start + veg) / 2;

    int min1 = minimum(t, start, kozep);
    int min2 = minimum(t, kozep+1, veg);

    if (min1 < min2)
        return min1;
    else
        return min2;
}

4. Határozzuk meg egy tömb legkisebb páros elemét divide et impera módszerrel (vagy térítsünk vissza -1-et, ha nincsenek párosak).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

int minimum(int t[], int start, int veg)
{
    if (start == veg) {
        if (t[start] % 2 == 0)
            return t[start];
        else
            return -1;
    }

    int kozep = (start + veg) / 2;

    int min1 = minimum(t, start, kozep);
    int min2 = minimum(t, kozep+1, veg);

    if (min1 == -1)
        return min2;
    else if (min2 == -1)
        return min1;
    else if (min1 < min2)
        return min1;
    else
        return min2;
}