Divide et Impera

  Metoda „Divide et Impera” este un procedeu recursiv de rezolvare al problemelor care pot fi descompuse în subprobleme de același tip ce se rezolvă mai ușor decât problema inițială; rezultatele obținute se combină pe parcurs pentru a-l formula pe cel final.

Fiind un procedeu recursiv, subproblemele trebuie să îndeplinească următoarele caracteristici:
• să fie de același tip cu problema principală (cea care se descompune);
• să fie mai ușoare, mai simple de rezolvat;
• să nu se intercaleze cu celelalte subprobleme.

  Este greu de descris un schelet al acestei metode, întrucât nu are formă fixă; este important de înțeles procedeul de ~dividere~ (de asemenea, un eventual schelet ar arăta complicat și descurajator).

Exemplu

Enunț: Să se afișeze numărul de elemente cu proprietatea P din vector.

bool P(int n){
...
}
int Numarare(int c1, int c2){
  int m;
  if(c1==c2) return P(v[c1]);
  m=(c1+c2)/2;
  return Numarare(c1,m) + Numarare(m+1,c2);
}

  Cum se rezolvă această problemă folosind metoda „Divide et Impera”? Vom divide vectorul în jumătăți, ținând minte cele două extremități (c1 este capătul din stânga, c2 este cel din dreapta).
  Variabila locală m va memora mijlocul celor două capete pentru a ne ajuta când descompunem în două subprograme mai mici (apeluri recursive).
  Atunci când, în cele din urmă, cele două capete devin egale, returnăm o verificare a proprietății cerute pentru oricare din capete; când sunt egale capetele, am ajuns la cea mai mică subproblemă posibilă (în cazul nostru un singur element din vector).

Nu am definit proprietatea din funcția P pentru a marca faptul că se poate pune orice proprietate simplă (palindrom, prim, suma cifrelor pară etc.)

Căutarea binară recursivă

  Metoda „Divide et Impera” este foarte utilă pentru a descrie algoritmul căutării binare.

int CautareB(int x, int c1, int c2){
  int m;
  if(c1>c2) return 0;
  else{
    m=(c1+c2)/2;
    if(x==V[m]) return m;
    else if(x<V[m]) return CautareB(x,c1,m-1);
    else return CautareB(x,m+1,c2);
  }
}

  Procedeul este asemănător cu varianta iterativă (nerecursivă), vom înjumătăți repetat șirul și apelăm recursiv jumătatea potrivită, până când elementul dorit este chiar mijlocul capetelor.