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?
- 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ă. - 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
- Caracteristici:
- Problemele trebuie să poată fi împărțite logic în subprobleme.
- Soluția completă trebuie să poată fi construită din soluțiile subproblemelor.
- 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
Avantaje | Dezavantaje |
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ă)
- Problema:
Găsiți poziția unui element într-un vector sortat. - 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.
- 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
- Problema:
Sortează un vector folosind metoda Divide et Impera. - Algoritm Divide et Impera:
- Împarte vectorul în două jumătăți.
- Sortează recursiv fiecare jumătate.
- Combină cele două jumătăți sortate.
- 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
- Problema:
Calculați xnx^nxn utilizând Divide et Impera. - 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.
- 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
- Scrieți un algoritm Divide et Impera pentru a găsi maximul și minimul unui vector.
- Implementați o funcție care determină suma elementelor unui vector folosind Divide et Impera.
- Realizați un program care rezolvă problema multiplicării matricelor prin metoda Divide et Impera.
8. Scheme logice
- Flux Divide et Impera:
- Start -> Împărțire problemă -> Rezolvare subprobleme -> Combinare rezultate -> Stop.
- 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ă.