Divide et Impera
Metoda Divide et Impera este o tehnică de programare ce presupune împărțirea unei probleme mai mari în subprobleme mai mici care se pot rezolva mai ușor, urmată de rezolvarea acestora in mod recursiv, iar, în final, prin combinarea soluțiilor subproblemelor se ajunge la soluția problemei inițiale.
Principiul de funcționare
- Divide (împarte): Problema inițială este împărțită în mai multe subprobleme mai mici, de acelasi tip. Procesul de împărțire continuă, fiecare subproblema fiind la rândul ei împărțită în mai multe subprobleme mai mici până când se ajunge la o problemă suficient de simplă pentru a fi rezolvată direct.
- Conquer (Rezolvă): Se rezolvă fiecare subproblemă, fie recursiv, daca este o problemă suficient de mare, fie direct, dacă am ajuns la un caz de bază care poate fi rezolvat simplu. (Exemplu: În căutarea binară căutarea se face recursiv doar într-una dintre jumătățile intervalului.)
- Combine (Combină): Rezultatele obținute ca soluții ale subproblemelor se combină, formându-se astfel soluția problemei inițiale.
Exemplu:
Să se sordoneze crescător un vector de N numere naturale prin metoda interclasării (Merge Sort):.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
|
#include
using namespace std;
// Funcția de interclasare (Merge)
void merge(int arr[], int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
// Creăm două subșiruri temporare
int L[n1], R[n2];
// Copiem datele în subșirurile temporare
for (int i = 0; i < n1; i++)
L[i] = arr[left + i];
for (int i = 0; i < n2; i++)
R[i] = arr[mid + 1 + i];
// Interclasăm subșirurile înapoi în arr[]
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
} else
{
arr[k] = R[j];
j++;
}
k++;
}
// Copiem elementele rămase din L[]
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
// Copiem elementele rămase din R[]
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
// Funcția de sortare Merge Sort
void mergeSort(int arr[], int left, int right)
{
if (left < right)
{
int mid = left + (right - left) / 2;
// Sortăm partea stângă
mergeSort(arr, left, mid);
// Sortăm partea dreaptă
mergeSort(arr, mid + 1, right);
// Combinăm cele două jumătăți sortate
merge(arr, left, mid, right);
}
}
int main()
{
int n;
// Citim numărul de elemente
cout << "Introduceti numarul de elemente: ";
cin >> n;
int arr[n];
// Citim elementele array-ului
cout << "Introduceti elementele: ";
for (int i = 0; i < n; i++)
cin >> arr[i];
// Apelăm Merge Sort
mergeSort(arr, 0, n - 1);
// Afișăm array-ul sortat
cout << "Array-ul sortat: ";
for (int i = 0; i < n; i++)
cout << arr[i] < " ";
return 0;
}
|
|
|
Intruduceti numarul de elemente ale vectorului: 6
Introduceti elementele (despartite de spatiu): 3 5 1 7 6 9
Array-ul sortat: 1 3 5 6 7 9
|
