Metoda divide et impera

#include <iostream>
#include <fstream>
using namespace std;

int x[101], n;

void citire() {
    ifstream f("minim.in");
    f >> n;
    for (int i = 1; i <= n; i++)
        f >> x[i];
    f.close();
}

Subprogramul citire()

• ifstream f("minim.in") deschide fișierul pentru citire
• se citesc n și cele n valori ale șirului, în x[1], …, x[n]
• f.close() închide fișierul

/* Minimul subsirului x[p..u]. */
int minim(int p, int u) {
    if (p == u)                 // un singur element
        return x[p];
    int m = (p + u) / 2;
    int min1 = minim(p, m);
    int min2 = minim(m + 1, u);
    if (min1 < min2)
        return min1;
    return min2;
}

Subprogramul minim(p, u)

• dacă subșirul are un singur element, adică p = u
  • problema admite rezolvare imediată: se returnează x[p]
• altfel
  • m este indicele din mijlocul intervalului [p, u]
  • min1 primește minimul subșirului x[p..m], prin autoapel
  • min2 primește minimul subșirului x[m+1..u], prin autoapel
  • se returnează cea mai mică dintre valorile min1 și min2

int main() {
    citire();
    cout << minim(1, n);
    return 0;
}

Programul principal

• se citesc datele din fișier
• se afișează minimul întregului șir, dat de apelul minim(1, n)

#include <iostream>
#include <fstream>
using namespace std;

int v[101], n, x;

/* Pozitia lui x in v[st..dr],
   sau 0 daca x nu se afla acolo. */
int cauta(int st, int dr) {
    if (st > dr)                // subsir vid: x nu exista
        return 0;
    int mij = (st + dr) / 2;
    if (v[mij] == x)
        return mij;
    if (x < v[mij])
        return cauta(st, mij - 1);   // jumatatea din stanga
    return cauta(mij + 1, dr);       // jumatatea din dreapta
}

Subprogramul cauta(st, dr)

• dacă st > dr, subșirul este vid
  • x nu se află în șir: se returnează 0
• mij este indicele din mijlocul intervalului [st, dr]
• dacă v[mij] este egal cu x
  • se returnează mij
• altfel, dacă x este mai mic decât v[mij]
  • se returnează rezultatul căutării în v[st..mij−1], prin autoapel
• altfel
  • se returnează rezultatul căutării în v[mij+1..dr], prin autoapel

Pozițiile încep de la 1, deci valoarea 0 nu poate fi o poziție și arată că x lipsește.

int main() {
    cin >> n >> x;
    for (int i = 1; i <= n; i++)
        cin >> v[i];

    ofstream g("cautare.out");
    int poz = cauta(1, n);
    if (poz == 0)
        g << "nu exista";
    else
        g << poz;
    g.close();
    return 0;
}

Programul principal

• se citesc n, x și cele n elemente ale șirului
• ofstream g("cautare.out") deschide fișierul pentru scriere
• poz primește rezultatul apelului cauta(1, n), pentru tot șirul
• dacă poz este 0
  • se scrie în fișier mesajul nu exista
• altfel
  • se scrie în fișier poz
• g.close() închide fișierul

#include <iostream>
using namespace std;

int n;

/* Muta n discuri de pe tija s pe tija d, folosind tija m. */
void hanoi(int n, int s, int d, int m) {
    if (n == 1)
        cout << s << " -> " << d << endl;
    else {
        hanoi(n - 1, s, m, d);     // n-1 discuri, pe m
        cout << s << " -> " << d << endl; // cel mai mare
        hanoi(n - 1, m, d, s);     // n-1 discuri, pe d
    }
}

Subprogramul hanoi(n, s, d, m)

• parametrii tijelor
  • s este tija sursă
  • d este tija destinație
  • m este tija intermediară
• dacă n = 1
  • problema admite rezolvare imediată: discul se mută de pe s pe d
• altfel
  • cele n − 1 discuri de deasupra se mută de pe s pe m, cu d ca tijă intermediară, prin autoapel
  • discul cel mai mare se mută de pe s pe d
  • cele n − 1 discuri se mută de pe m pe d, cu s ca tijă intermediară, prin autoapel

int main() {
    cin >> n;
    hanoi(n, 1, 2, 3);
    return 0;
}

Programul principal

• se citește n
• se mută cele n discuri de pe tija 1 pe tija 2, cu tija 3 ca tijă intermediară

#include <iostream>
using namespace std;

int v[101], a[101], n;

/* Interclaseaza v[st..mij] si v[mij+1..dr],
   ordonate crescator. */
void interclasare(int st, int mij, int dr) {
    int i = st, j = mij + 1, k = 0;
    while (i <= mij && j <= dr)
        if (v[i] <= v[j])
            a[++k] = v[i++];
        else
            a[++k] = v[j++];
    while (i <= mij)            // ce a ramas in stanga
        a[++k] = v[i++];
    while (j <= dr)             // ce a ramas in dreapta
        a[++k] = v[j++];
    for (i = st, k = 1; i <= dr; i++, k++)
        v[i] = a[k];            // inapoi in v
}

Subprogramul interclasare(st, mij, dr)

• i parcurge subșirul din stânga, v[st..mij], iar j subșirul din dreapta, v[mij+1..dr]
• cât timp ambele subșiruri mai au elemente
  • cel mai mic dintre v[i] și v[j] se adaugă în vectorul auxiliar a, iar indicele lui înaintează
  • a[++k] = v[i++] mărește întâi k, pune v[i] pe poziția k și apoi mărește i
• elementele rămase într-unul dintre subșiruri se adaugă la sfârșitul lui a
• elementele din a se copiază înapoi în v, pe pozițiile de la st la dr

void mergesort(int st, int dr) {
    if (st < dr) {
        int mij = (st + dr) / 2;
        mergesort(st, mij);
        mergesort(mij + 1, dr);
        interclasare(st, mij, dr);
    }
}

Subprogramul mergesort(st, dr)

• dacă subșirul v[st..dr] are cel puțin două elemente
  • mij este indicele din mijlocul intervalului
  • se ordonează v[st..mij], prin autoapel
  • se ordonează v[mij+1..dr], prin autoapel
  • se interclasează cele două subșiruri ordonate
• un subșir cu un singur element este deja ordonat: subprogramul nu face nimic

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    mergesort(1, n);
    for (int i = 1; i <= n; i++)
        cout << v[i] << " ";
    return 0;
}

Programul principal

• se citesc n și cele n elemente ale șirului
• se ordonează tot șirul, prin apelul mergesort(1, n)
• se afișează șirul ordonat

#include <iostream>
using namespace std;

int v[101], n;

void schimba(int& a, int& b) {
    int aux = a;
    a = b;
    b = aux;
}

Subprogramul schimba(a, b)

• interschimbă valorile variabilelor a și b, cu ajutorul variabilei aux
• a și b se transmit prin referință, int&, ca schimbarea să se vadă după apel

/* Aseaza pivotul v[st] pe pozitia lui din sirul ordonat
   si furnizeaza acest loc prin parametrul mij. */
void pozitie(int st, int dr, int& mij) {
    int i = st, j = dr, pi = 0, pj = 1;
    while (i < j) {
        if (v[i] > v[j]) {
            schimba(v[i], v[j]);
            schimba(pi, pj);    // se misca celalalt capat
        }
        i = i + pi;
        j = j - pj;
    }
    mij = i;
}

Subprogramul pozitie(st, dr, mij)

• i pornește de la st, iar j de la dr
• pi și pj arată care indice se mișcă: la început pi = 0 și pj = 1, deci se mișcă numai j
• cât timp i < j
  • dacă v[i] > v[j], cele două elemente sunt în ordine greșită
    • se interschimbă v[i] și v[j]
    • se interschimbă pi și pj, deci de acum se mișcă celălalt indice
  • i crește cu pi, iar j scade cu pj
• pivotul se află mereu pe poziția indicelui care nu se mișcă
• când i și j se întâlnesc, pivotul este pe poziția lui din șirul ordonat: mij primește i

void quicksort(int st, int dr) {
    int mij;
    if (st < dr) {
        pozitie(st, dr, mij);
        quicksort(st, mij - 1);
        quicksort(mij + 1, dr);
    }
}

Subprogramul quicksort(st, dr)

• dacă subșirul v[st..dr] are cel puțin două elemente
  • pivotul se așază pe poziția lui din șirul ordonat, mij
  • se ordonează subșirul din stânga pivotului, v[st..mij−1], prin autoapel
  • se ordonează subșirul din dreapta pivotului, v[mij+1..dr], prin autoapel
• un subșir cu cel mult un element este deja ordonat

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i];
    quicksort(1, n);
    for (int i = 1; i <= n; i++)
        cout << v[i] << " ";
    return 0;
}

Programul principal

• se citesc n și cele n elemente ale șirului
• se ordonează tot șirul, prin apelul quicksort(1, n)
• se afișează șirul ordonat