Tot asa, se elaboreaza un algoritm prin divide et imoera: la un anumit nivel avem doua posibilitati:
am ajuns la o problema care admite o rezolvare imediata, caz in care se rezolva si se revine din apel(conditia de terminare);
nu am ajuns in situatia de la punctul 1, caz in care sdescompunem problema in doua sau mai multe subprobleme, pentru fiecare din ele reapelam functia, combinam rezultatele si revnim din apel.
Aplicatii
Maximul dintr-un vector
Se citeste un vector cu n componente, numere naturale. Se cere sa se tipareasca valoare maxima.
Trebuie tiparita valoarea maxima dintre numerele retinute in vector de la i la j(initial i= 1, j=n). Pentru aceasta procedam astfel :
daca i=j, valoare maxima va fi v[i] ;
contrar vom imparti vectorul in doi vectori (primul vector va contine componentele de la i la (i+j) div 2, al doilea va contine componentele de la ((i+j) div 2 +1 la j ) , rezolvam subproblemele (aflam maximul pentru fiecare din ele) iar solutia problemei va fi data de valoarea maxima dintre rezultatele celor doua subprobleme.
#include
int v[10],n;
int max(int i ,int j)
{ int a,b;
if (i==j) return v[i] ;
else
{ a=max(i, (i+j)/2);
b=max((i+j)/2+1,j);
if (a>b) return a;
else return b;
}
}
main( )
{ cout<<"n=";cin>>n;
for (int i=1;i<=n;i++)
{cout<<"v["<>v[i]; }
cout<<"max="<
}
Cautare binara
Se citeste un vector cu n componente numere intregi, unde nemerele se presupun ordonate crescator si o valoare intreaga (nr). Sa se decida daca nr se gaseste sau nu printre numerele citite, iar in caz afirmativ sa se tipareasca indicele componentei care contine acea valoare .
O rezolvare in care nr se compara pe rand cu cele n valori, este lipsita de valoare (nu exploateaza faptul ca cele n valori sunt in secventa crescatoare). Algoritmul care va fi propus este mult mai performant si face parte, asa cum am invatat, dintre algoritmii clasici.
Problema este de a decide daca valoarea cautata se gaseste printre numerele de indice cuprins intre i si j (intial i=1, j=n ). Pentru aceasta vom proceda astfel:
daca nr coincide cu vloarea de indice (i+j)/2 ( valoarea de la mijloc ) , se tipaeste indicele si se revine din apel (problema a fost rezolvata).
Contrar, daca i
daca numaul este mai mic decat valoarea testata (din mijloc), inseamna ca avem sanse sa-l gasim intre componentele cu indicele intre i si (i+j)/2-1 , caz in care reapelam functia cu acesti parametri
daca numarul este mai mare decat valoarea testata (din mijloc), inseamna ca avem sanse sa-l gasim intre componentele cu indicele intre (i + j)/2+1 si j , caz in care reapelam functia cu acesti parametri.
Problema nu se descompune in altele care se rezolva, dupa care nu se compara solutia, ci se reduce la o subproblema. In linii mari , acest rationament este de tip Divide et impera.
#include
int v[100],n,nr;
void caut(int i, int j)
{ if (nr==v[(i+j)/2])
cout<<"gasit"<<' '<<"indice"<<(i+j)/2;
else
if (i
if (nr
caut (i , (i+j)/2-1;
else caut ((i+j)/2+1,j);
};
main ( )
{ cout<<"n=";cin>>n;
for (int i=1;i<=n;i++)
{ cout<<"v["<>v[i];}
cout<<"nr=";cin>>nr;
caut (1,n);
}
Sortarea prin interclasare
Se considera vectorul a cu n componente numere intregi ( sau reale ). Sa se sorteze crescator, utilizand sortarea prin interclasare.
Daca dispunem de doua siruri de valori, primul cu m elemente, al diolea cu n elemente, ambele sortate, atunci se poate obtine un vector care contine toate valorile soratate. Algoritmul de interclasare este performant, pentru ca efectueaza cel mult m+n-1 comparatii.
Algoritmul de sortare prin interclasare se bazeaza pe urmatoarea idee: pentru a sorta un vector cu n elemente il impatim in doi vectori care, odata sortati, se interclaseaza.
