Metoda „Divide et Impera”

Aplicaţii de laborator (C++)

Probleme rezolvate• 1.Turnurile din Hanoi• 2. Algoritmul căutării binare (Binary Search)• 3. Calculul radicalului de ordinul 2• 4. Rezolvarea unei ecuaţii• 5. Exponenţiere rapidă• 6. Algoritmul sortării rapide (QuickSort)• 7. Algoritmul de sortare prin interclasare (MergeSort)

1. Turnurile din HanoiSe dau 3 tije simbolizate prin a, b, c. Prin tija a se găsesc discuri de diametre diferite, aşezate în ordine crescătoare a diametrelor privite de jos în sus. Se cere să se mute discurile de pe tija a pe tija b, utilizând ca tijă intermediară tija c, respectând următoarele reguli:- la fiecare pas se mută un singur disc;- nu este permis să se aşeze un disc cu diametrul mai mare peste un disc cu diametrul mai mic.Rezolvare: Dacă n = 1 se face mutarea ab, adică se mută discul de pe tija a pe tija b. Dacă n = 2 se fac mutările ac, ab, cb. În cazul în care n>2 problema se complică. Notăm cu H(n, a, b, c) şirul mutărilor celor n discuri de pe tija a pe tija b, utilizând ca tijă intermediară, tija c. Conform strategiei Divide et impera încercăm să descompunem problema în alte două subprograme de acelaşi tip, urmând apoi combinarea soluţiilor. În acest sens, observăm că mutarea celor n discuri de pe tija a pe tija b, utilizând ca tijă intermediară tija c, este echivalentă cu:- mutarea a n-1 discuri de pe tija a pe tija c, utilizând ca tijă intermediară tija b;- mutarea discului rămas pe tija b;- mutarea a n – 1 discuri de pe tija c pe tija b, utilizând ca tijă intermediară tija a.

RezolvareParcurgerea celor trei etape permite definirea recursivă a şirului H(n, a, b, c) astfel:

ExemplePentru n = 2 avem: H(2, a, b, c) = H(1, a, c, b), ab, H(1, c, b, a)= = ac, ab, cb. Pentru n = 3 avem:H(3, a, b, c) = H(2, a, c, b), ab, H(2, c, b, a) = H(1, a, b, c) ac, H(1, b, c, a) ab, H(1, c, a, b) cb, H(1, a, b, c) = ab, ac, bc, ab, ca, cb, ab.

Animaţie: pentru n=4

A B C

A B C

A B C

Program hanoi.cpp

2. Căutarea binarăSe citesc elementele vectorului v ordonate crescător şi x un număr întreg. Verificaţi dacă x apare în vector, şi determinaţi indicele pe care apare sau -1 dacă x nu apare în vector.Rezolvare:Notăm cu a vectorul sortat crescător şi cu x valoarea de căutat, iar cu s indicele de început şi cu d indicele ultimului element din secvenţa de elemente în care căutăm valoarea x, adică a[s],…,a[d]. La fiecare repetare renunţăm la jumătate din elementele rămase din vector. Algoritmul căutării binare se aplică astfel:P1. Iniţial, limitele sunt s=1 şi d =n (toate elementele din vector)P2. La fiecare repetare, determinăm indicele elementului median, m=(s+d)/2. Comparăm elementul din mijloc cu valoarea m, adică a[m] <= xCondiţia este Adevărată: continuăm cu jumătatea din dreapta a vectorului, s=mCondiţia este Adevărată: continuăm cu jumătatea din dreapta a vectorului, d=m-1

Exemplu

6

58

3

27

9

81

1

3

2

10

4

31

5

42

7

63

2

10

2

10

2

10

2

10

Pentru n=12 şi vectorul 3,10,27,31,42,58,63,75,81,94,101,149

1 2 3 4 5 6 7 8 9 10 11 12 3 10 27 31 42 58 63 75 81 94 101 149

Rezolvare – căutarea binară

3. Radicalul de ordinul 2Calculaţi radicalul de ordinul 2 (rădăcina pătrată) cu 4 zecimale exacte, pentru un număr n dat.Rezolvare:Se aplică metoda căutării binare:-ştim că radicalul lui n are o valoarecuprinsă între 1 şi n, 1 r2 n-pentru un interval a, b calculăm valoarea mediană m:a) dacă |m*m-n|, ne oprim este precizia urmărită;b) Dacă m*mn continuăm căutareaîn intervalul [m,b], altfel continuămcu intervalul [a,m]

4. Rezolvarea unor ecuaţii• Metoda bisecţiei, numită uneori şi metoda dihotomiei sau a înjumătăţirii

intervalelor, este cea mai simplă dintre metodele de rezolvare a ecuaţiilor algebrice şi transcendente. Se consideră că, printr-un procedeu oarecare, s-a reuşit localizarea rădăcinii exacte x0 a ecuaţiei f(x)=0 în intervalul [a, b]. În ipoteza în care funcţia f(x) este continuă, iar radacina x0 este singurul zerou al lui f(x) în [a, b], la extremităţile intervalului funcţia ia valori de semne contrare: f(a) * f(b)<0. Soluţia ecuaţiei este determinată printr-un algoritm asemănător algoritmului căutării binare.

Metoda bisecţiei intervalului1. // Scrieti un program care sa rezolve 2. // cu metoda "Divide et Impera" ecuatia: 3. // x^3-3*x+1=0 4. //Cautam solutiile in intervalele: 5. //[-2,-1],[0,1],[1,2] 6. #include<iostream> 7. #include<cmath> 8. using namespace std; 9. double f(double x) 10. { 11. return x*x*x-3*x+1; 12. } 13. double Sol(double a,double b) 14. { 15. double m=(a+b)/2; 16. if(fabs(b-a)<=0.0001) return m; 17. if(f(a)*f(m)<0) return Sol(a,m); 18. if(f(m)*f(b)<0) return Sol(m,b); 19. } 20. int main() 21. { 22. cout<<"Solutiile ecuatiei: x^3-3*x+1=0"<<endl; 23. cout<<"x1= "<<Sol(-2,-1)<<endl; 24. cout<<"x2= "<<Sol(0,1)<<endl; 25. cout<<"x3= "<<Sol(1,2)<<endl; 26. return 0; 27. }

5. Exponenţiere rapidă• Calculul valorii xn poate fi

efectuat cu mai puţin de n-1 operaţii de înmulţire

• Definim recursiv operaţia de ridicare la puterea n:

x10=(x5)2=(x(x2)(x2))2

6. Algoritmul QuickSort

Se citesc cele n elemente ale vectorului v=(v[1], v[2], …,v[n]). Ordonaţi crescător elementele vectorului.Rezolvare: Problema ordonării sau sortării este o problemă deosebit de importantă în practică. Algoritmul sortării rapide – QuickSort, foloseşte tehnica Divide et Impera pentru sortare:-se alege o valoare numită pivot, în mod ideal cât mai aproape de valoarea mediană din vector- se interschimbă elemente din vector până când vectorul se partiţionează în două segmente, cu elemente mai mici (în partea stângă) şi elemente mai mari (în partea dreaptă) decât pivotul-se apelează recursiv algoritmul pentru cele două partiţii (vectori) mai mici obţinute

Programul qsort.cpp

7. Sortare prin interclasare

Se considera vectorul a cu n componente nr intregi(sau reale).Sa se sorteze crescator utilizand sortarea prin interclasareRezolvare: Algoritmul de sortare prin interclasare se bazeaza pe urmatoarea idee:pt a sorta un vector cu n elemente il impartim in doi vectori care,odata sortati,se interclaseaza.

Rezolvare – sortarea prin interclasare