Logo Încarcă | Propune
Conecteaza-te arrow

Divide et Impera - programe şi algoritmi cu acest procedeu recursiv

Divide et Impera este o metodă folosită la mulți algoritmi importanți în limbajele de programare. Termenul provine din limba latină, însemnând "divide și conduce", după ideea de a putea conduce mai ușor o mulțime de oameni care nu sunt aliați între ei.

Ca metodă de lucru, ea se bazează pe înjumătățirea repetată a problemei în subprobleme pentru a scurta durata de execuție a programului. Rezolvarea problemei va fi, în mod logic, "reuniunea" subproblemelor.

În primă instanță, o abordare a acestei metode este implementată în algoritmul de sortare Merge Sort. Astfel, fiind un vector nesortat de n elemente, în loc să îl sortăm prin interschimbare a fiecărei valori prin metoda Bubble Sort sau "Metoda bulelor" (complexitate O(n2) ), îmjumătățim repetat vectorul, sortând jumătățile separat, după care le interclasăm, obținând în final vectorul sortat (complexitatea metodei Merge Sort este O(n * log n) ).

O altă utilizare a aceste metode este în cadrul algoritmului de căutare binară. Amintesc că acest algoritm este folosit pentru a găsi poziția unui element cu o anumită proprietate fiind dat un vector de n elemente nesortat. Pentru a folosi căutarea binară, trebuie întâi să sortăm vectorul. Acesta fiind sortat, algoritmul de căutare binară înjumătățește repetat vectorul, verificând la fiecare înjumătățire dacă elementul căutat este "înainte" sau "după" jumătate. În mod evident, este mult mai rapid să găsești poziția unui element înjumătățind vectorul repetat (O(n * log n) ) decât să-l parcurgi pas cu pas, poziție cu poziție ( O(n) ).

 

Ca în imaginea de mai sus, dorim să găsim poziția lui x în cel mai scurt mod. În loc să parcurgem pas cu pas vectorul de la început până la x (care poate fi chiar și ultimul element al vectorului), împărțim vectorul în 2 și verificăm în care din jumătăți se află x-ul nostru. În acest exemplu, după prima înjumătățire, știm că x-ul nostru se află la stânga față de n/2. Lăsăm ce este la dreapta de n/2, și înjumătățim din nou. Ajungem la n/4, verificăm unde este x-ul și știm că x-ul este la stânga de n/4. Din nou, lăsăm ce se află la dreapta de n/4 și iar înjumătățim. Astfel ajungem la n/8 și știm că x-ul se află la dreapta de n/8. Lăsăm ce este la stânga de n/8 și înjumătățim ce este la dreapta de n/8, ajungând la n/16, ș.a.m.d.

Algoritmul de căutare binară (recursiv):


 

int n,x,v[10],m;
int caut (int s, int d)
{
    if(s>d)
        return -1;
    else
        {
            m =(s+d)/2;
            if (x==v[m])
                return m;
            if (x<v[m])
                return caut(s,m-1);
            else
                return caut(m+1,d);
        }
}

int main()
{  
    cout<<"n,x ";
    cin>>n>>x;
    cout<<"dati "<<n<<" elemente (in ordine crescatoare).\n";
    for (int i=1;i<=n;i++)
        cin>>v[i];
    cout<<"elementul "<<x<<" a fost gasit pe pozitia: "<<caut (1,n);
    return 0;

 

Divide et Impera are multiple alte aplicații, printre care și înmulțirea a două matrici considerând fiecare matrice ca un produs de n/2 * n/2 elemente, înmulțirea numerelor foarte mari și metoda de sortare rapidă (Quick Sort), de asemenea foarte eficientă.


Cuvinte cheie: sortare vectori prin metoda bublle sort, algoritmi divide et impera, cautarea binara divide et impera, cautare binara,cautarea binara pozitie divide et impera, ce este Divide et Impera, Divide et Impera, algoritmul Divide et Impera, metoda Divide et Impera, cautare binara, functie cautare binara, recursivitate, functie recursiva, Merge Sort,divide și conduce, Bublle Sort, mingw, problema sortare, sortare Divide Et Impera, qsort, algoritm sortare, program sortare, program sortare vector c++, sortare vector c++, cum sortez un array


Detalii:
De acelasi autor:
Autor: ana_anutza - Trimite mesaj autorului
Categoria: C




Comentarii:
Nume/Prenume
Email
Mesaj
Da :D :-N

Postat de ana_anutza la 2011-03-03 23:22:24
Felicitări ! Ai revenit în sistem :D :-N

Postat de Cristy la 2011-03-03 21:53:06
© Biblioteca de tutoriale Limbă - Aplicaţii - Realizatori- Tutoriale - Contact - Privacy Policy