Divide et Impera
Divide et impera se bazează pe principiul descompunerii problemei în două sau mai multe subprobleme (mai ușoare), care se rezolvă, iar soluția pentru problema inițială se obține combinând soluțiile subproblemelor. De multe ori, subproblemele sunt de același tip și pentru fiecare din ele se poate aplica aceeași tactică a descompunerii în (alte) subprobleme, până când (în urma descompunerilor repetate) se ajunge la probleme care admit rezolvare imediată.
Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici. Se poate afirma că numărul celor rezolvabile prin “divide et impera” este relativ mic, tocmai datorită cerinței ca problema să admită o descompunere repetată.
Divide et impera este o tehnică ce admite o implementare
recursivă. Principiul general prin care se elaborează algoritmi recursivi este: “ce se întâmplă la un nivel, se întâmplă la orice nivel” (având grijă să asigurăm condițiile de terminare). Așadar, un algoritm prin divide et impera se elaborează astfel: la un anumit nivel avem două posibilități:
- s-a ajuns la o problemă care admite o rezolvare imediată (condiția de terminare), caz în care se rezolvă și se revine din apel;
- nu s-a ajuns în situația de la punctul 1, caz în care problema curentă este descompusă în (două sau mai multe) subprobleme, pentru fiecare din ele urmează un apel recursiv al funcției, după care combinarea rezultatelor are loc fie pentru fiecare subproblemă, fie la final, înaintea revenirii din apel.
Aplicații
Se citește un vector cu n componente, numere naturale. Se cere să se tipărească valoarea maximă.
Funcția căutată va genera valoarea maximă dintre numerele reținute în vector pe o poziție dintre i și j (inițial, i=1, j=n). Pentru aceasta, se procedează astfel:
- dacă i=j, valoarea maxima va fi v[i];
- în caz contrar, se imparte vectorul în doi subvectori - presupunem varianta pentru paralelizare pe 2 procesoare. Se calculează mijlocul m al intervalului [i, j]: m = (i+j) div 2. Primul subvector va conține componentele de la i la m, al doilea va conține componentele de la (m+1) la j; se rezolvă subproblemele (aflându-se astfel maximul pentru fiecare din subvectori), iar soluția curentă va fi dată de valoarea maximă dintre rezultatele celor două subprobleme.
#include <iostream>
using namespace std;
int v[10], n;
int max(int i, int j) {
int a, b, m;
if (i == j)
return v[i];
else {
m = (i + j) / 2;
a = max(i, m);
b = max(m + 1, j);
if (a > b)
return a;
else
return b;
}
}
int main() {
cout <<”n =”;
cin >> n;
for (int i = 1; i <= n; i++) {
cout<<"v["<cin>>v[i];
}
cout<<"max="<1,n);
return 0;
}
Căutare binară
Se citește un vector cu n componente numere întregi (numerele se presupun ordonate crescător) și o valoare întreagă (“nr”). Să se decidă dacă nr se găsește sau nu printre numerele citite, iar în caz afirmativ să se tipărească indicele componentei care conține această valoare.
O rezolvare în care nr se compară pe rând cu toate cele n componente reperzintă o pierdere de performanță (nu exploatează faptul că cele n valori sunt în secvență crescătoare). Algoritmul care va fi propus este optim și se poate spune că face parte dintre algoritmii “clasici”.
Funcția care va fi implementată va decide dacă valoarea căutată se găsește printre numerele aflate pe poziții de indice cuprins între i și j (inițial, i=1, j=n). Pentru aceasta, se va proceda astfel:
- dacă nr coincide cu valoarea de la mijloc, aflată pe poziția de indice (i+j)/2, se tipărește indicele și se revine din apel (problema a fost rezolvată).
- în caz contrar, dacă mai sunt și alte elemente de analizat (adică i
- dacă nr este mai mic decât valoarea testată (din mijloc), înseamnă că nu se poate afla pe pozițiile din partea dreaptă, întrucât acestea sunt cel puțin mai mari decât valoarea testată. Nr se poate găsi doar printre componentele cu indice între i și (i+j)/2 - 1, caz în care se reapelează funcția cu acești parametri;
- dacă nr este mai mare decât valoarea testată (din mijloc), înseamnă că nu se poate afla în stânga; se poate găsi doar printre componentele cu indicele între (i+j)/2 + 1 și j, caz în care se reapelează funcția cu acești parametri.
- dacă nu mai sunt alte elemente de analizat (pentru că i=j și valoarea din mijloc, v[i], nu coincide cu nr), se concluzionează că nr nu apare în cadrul vectorului.
Această problemă nu mai necesită analiza tuturor subproblemelor în care se descompune, ea se reduce la o singură subproblemă, iar partea de combinare a soluțiilor dispare. În linii mari, această rezolvare este tot de tip “divide et impera”.
#include <iostream>
using namespace std;
int v[100], n, nr;
void caut(int i, int j) {
int m = (i + j) / 2;
if (nr == v[m])
cout <<”gasit, indice =”<< m;
else if (i < j)
if (nr < v[m])
caut(i, m - 1);
else
caut(m + 1, j);
else
cout <<”nu a fost gasit.”;
}
int main() {
cout <<”n =”;
cin >> n;
for (int i = 1; i <= n; i++) {
cout <<”v[“<< i <<”] =”;
cin >> v[i];
}
cout <<”nr =”;
cin >> nr;
caut(1, n);
return 0;
}
QUICKSORT
Functia poz rezolva o portiune din vector cuprinsa intre indicii p si u piv=v[p] este un reper.La sfarsitul executiei acestei functii piv se va gasi pe o pozitie k cuprinsa intre p si u astfel incat toate componentele vectorului cuprinse intre p si k-1 vor fi mai mici decat piv iar componentele cuprinse intre k+1 si u vor fi mai mari decat piv. Deci piv se va gasi pe pozitia k corespunzatoare ordinii in vector
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
int x[2000], n;
int poz(int p, int u) {
int piv, aux, k;
piv = x[p];
while (p < u) {
if (x[p] > x[u]) {
aux = x[p];
x[p] = x[u];
x[u] = aux;
}
if (x[p] == piv)
u--;
else
p++;
}
k = p;
return k;
}
void quick(int p, int u) {
int k;
if (p < u) {
k = poz(p, u);
quick(p, k - 1);
quick(k + 1, u);
}
}
void main() {
clrscr();
cout << "n=";
cin >> n;
for (int i = 1; i <= n; i++) {
cout << "x[" << i << "]=";
cin >> x[i];
}
quick(1, n);
for (i = 1; i <= n; i++) cout << x[i] << ' ';
getch();
}
TURNURILE DIN HANOI
Turnurile Din Hanoi
PROBLEME PROPUSE
1. Se citeste un numar natural n si n numere naturale. Sa se calculeze cel mai mare divizor comun al celor n numere, folosind un algoritm Divide et Impera.
2. Scrieti un program pentru determinarea minimului dintr-un sir de numere intregi, folosind Divide et Impera.
3. Scrieti un program pentru calculul sumei valorilor dintr-un sir de numere intregi, folosind Divide et Impera.
4. Sa se determine cate elemente pare are un vector
5. Fie un tablou neordonat de numere intregi. Sa se determine prin metoda D&I de cate ori apare in tablou o anumita valoare v.
6. Să se calculeze n!
7. Să se calculeze simultan produsul şi suma a n numere memorate într-un vector.
8. Să se calculeze suma 1x2+2x3+3x4+…+nx(n+1).
9. Să se calculeze suma 1x2+1x2x3+…+1x2x3x…xn.
10. Să se numere elementele divizibile cu 5 dintr-un vector.
11. Să se verifice dacă un vector conţine numai numere pozitive sau numai numere negative.
12. Sa se gaseasca intr-un vector cu n elemente un element cu proprietatea ca valoarea lui este egala cu pozitia pe care apare. (a[k]=k)
13. Scrieti o functie ce inverseaza un sir de caractere
14. Să se afişeze dacă un cuvânt este palindrom.
15. Să se verifice dacă un şir de numere este simetric.
16. Sa se determine valoarea unui polinom intr-un punct
17. Se citesc numele si inaltimile a n persoane.
a) Sa se afiseze persoanele avand inaltimea mai mare sau egala cu un h citit.
b) Sa se ordoneze crescator persoanele dupa inaltime.
c) Sa se afiseze o persoana avand o inaltime data. Daca nu exista o astfel de persoana se va afisa un mesaj.
18. Se citesc numele a n persoane si inaltimile
a) Sa se determine daca persoanele sunt ordonate dupa inaltime
b) Sa se afiseze persoana cea mai inalta
c) Care este inaltimea medie?
d) Sa se ordoneze alfabetic persoanele prin metoada QuickSort
e) Sa se afiseze inaltimea unei persoane al carei nume se va citi de la tastatura (cautare binara dupa nume)
f) Sa se ordoneze persoanele descrescator dupa inaltime utilizand MergeSort
g) Sa se afiseze toate persoanele cu inaltimea mai mare de 1.70
h) Sa se determine cate persoane au inaltimea 1.80