|

Metoda Divide et Impera în Programare 3


1. Obiectivele lecției:

  • Să înțeleagă conceptul metodei Divide et Impera.
  • Să învețe cum să rezolve probleme mari prin împărțirea lor în subprobleme mai mici.
  • Să implementeze exemple practice utilizând această metodă.

2. Ce este metoda Divide et Impera?

  1. Definiție:
    Metoda Divide et Impera (Divide and Conquer) este o tehnică de programare care împarte o problemă mare în subprobleme mai mici, le rezolvă separat și apoi combină rezultatele pentru a obține soluția finală.
  2. Etapele metodei:
    • Divide (Împărțire): Împarte problema în una sau mai multe subprobleme mai mici.
    • Conquer (Rezolvare): Rezolvă subproblemele. Dacă sunt suficient de mici, rezolvarea este directă.
    • Combine (Combinare): Combină soluțiile subproblemelor pentru a forma soluția problemei inițiale.

3. Caracteristici și aplicabilitate

  1. Caracteristici:
    • Problemele trebuie să poată fi împărțite logic în subprobleme.
    • Soluția completă trebuie să poată fi construită din soluțiile subproblemelor.
  2. Probleme rezolvate prin Divide et Impera:
    • Sortarea (Merge Sort, Quick Sort).
    • Căutarea (Binary Search).
    • Probleme de geometrie computațională.
    • Probleme pe arbori și grafuri.

4. Avantaje și dezavantaje

AvantajeDezavantaje
Reduce complexitatea problemelor mari.Poate consuma mai multă memorie (recursivitate).
Ușor de paralelizat.Necesită o analiză atentă pentru combinare.
Aplicabilitate largă.Nu toate problemele pot fi împărțite logic.

5. Exemple practice


Exemplu 1: Binary Search (Căutarea binară)

  1. Problema:
    Găsiți poziția unui element într-un vector sortat.
  2. Algoritm Divide et Impera:
    • Împărțiți vectorul în două jumătăți.
    • Comparați elementul căutat cu elementul din mijloc.
    • Continuați căutarea în jumătatea corespunzătoare.
  3. Implementare:

#include <iostream>

using namespace std;

int binarySearch(int arr[], int st, int dr, int x) {

    if (st <= dr) {

        int mijloc = st + (dr – st) / 2;

        if (arr[mijloc] == x) return mijloc;

        if (arr[mijloc] > x) return binarySearch(arr, st, mijloc – 1, x);

        return binarySearch(arr, mijloc + 1, dr, x);

    }

    return -1;

}

int main() {

    int arr[] = {2, 3, 4, 10, 40};

    int n = sizeof(arr) / sizeof(arr[0]);

    int x = 10;

    int rezultat = binarySearch(arr, 0, n – 1, x);

    if (rezultat != -1) {

        cout << „Elementul se află la indexul ” << rezultat << endl;

    } else {

        cout << „Elementul nu a fost găsit.” << endl;

    }

    return 0;

}


Exemplu 2: Merge Sort

  1. Problema:
    Sortează un vector folosind metoda Divide et Impera.
  2. Algoritm Divide et Impera:
    • Împarte vectorul în două jumătăți.
    • Sortează recursiv fiecare jumătate.
    • Combină cele două jumătăți sortate.
  3. Implementare:

#include <iostream>

using namespace std;

void interclasare(int arr[], int st, int mijloc, int dr) {

    int n1 = mijloc – st + 1;

    int n2 = dr – mijloc;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++) L[i] = arr[st + i];

    for (int i = 0; i < n2; i++) R[i] = arr[mijloc + 1 + i];

    int i = 0, j = 0, k = st;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) arr[k++] = L[i++];

        else arr[k++] = R[j++];

    }

    while (i < n1) arr[k++] = L[i++];

    while (j < n2) arr[k++] = R[j++];

}

void mergeSort(int arr[], int st, int dr) {

    if (st < dr) {

        int mijloc = st + (dr – st) / 2;

        mergeSort(arr, st, mijloc);

        mergeSort(arr, mijloc + 1, dr);

        interclasare(arr, st, mijloc, dr);

    }

}

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr) / sizeof(arr[0]);

    mergeSort(arr, 0, n – 1);

    cout << „Vectorul sortat: „;

    for (int i = 0; i < n; i++) cout << arr[i] << ” „;

    cout << endl;

    return 0;

}


Exemplu 3: Puterea unui număr

  1. Problema:
    Calculați xnx^nxn utilizând Divide et Impera.
  2. Algoritm Divide et Impera:
    • Împărțiți exponența nnn în jumătăți.
    • Reduceți problema la xn/2x^{n/2}xn/2.
  3. Implementare:

#include <iostream>

using namespace std;

int putere(int x, int n) {

    if (n == 0) return 1;

    int jumatate = putere(x, n / 2);

    if (n % 2 == 0) return jumatate * jumatate;

    else return x * jumatate * jumatate;

}

int main() {

    int x = 2, n = 10;

    cout << x << „^” << n << ” = ” << putere(x, n) << endl;

    return 0;

}


7. Activități practice pentru elevi

  1. Scrieți un algoritm Divide et Impera pentru a găsi maximul și minimul unui vector.
  2. Implementați o funcție care determină suma elementelor unui vector folosind Divide et Impera.
  3. Realizați un program care rezolvă problema multiplicării matricelor prin metoda Divide et Impera.

8. Scheme logice

  1. Flux Divide et Impera:
    • Start -> Împărțire problemă -> Rezolvare subprobleme -> Combinare rezultate -> Stop.
  2. Exemplu vizual pentru Merge Sort:
    • Pasul 1: Împarte vectorul.
    • Pasul 2: Sortează fiecare jumătate.
    • Pasul 3: Interclasează rezultatele.

9. Concluzie

  • Divide et Impera este o metodă eficientă pentru a rezolva probleme complexe prin reducerea lor la subprobleme mai simple.
  • Este aplicabilă în sortare, căutare și alte probleme algoritmice.
  • Practica ajută la identificarea problemelor care pot fi rezolvate eficient folosind această tehnică.

Similar Posts

Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile obligatorii sunt marcate cu *