Metoda „Divide et Impera”

Aplicaţii de laborator (C++)

Probleme rezolvate

• 1.Turnurile din Hanoi

• 2. Algoritmul căutării binare

• 3. Calculul radicalului de ordinul 2

• 4. Rezolvarea unei ecuaţii

• 5. Exponenţiere rapidă

• 6. Algoritmul sortării rapide (QuickSort)

1. Turnurile din Hanoi Se 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.

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

𝑯 𝒏, 𝒂, 𝒃, 𝒄 = 𝒂𝒃, 𝑯 𝒏 − 𝟏, 𝒂, 𝒄, 𝒃 , 𝒂𝒃,𝑯 𝒏 − 𝟏, 𝒄, 𝒃, 𝒂 ,

𝒏 = 𝟏 𝒏 > 𝟏

Exemple

Pentru 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] <= x Condiţia este Adevărată: continuăm cu jumătatea din dreapta a vectorului, s=m Condiţ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 2

Calculaţ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 valoare

cuprinsă î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ăm

cu 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 intervalului 1. // 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:

• 𝑥𝑛 =

1,

𝑥𝑘 ∙ 𝑥𝑘 ,

𝑥 ∙ 𝑥𝑘 ∙ 𝑥𝑘 ,

𝑛 = 0𝑛 = 2𝑘

𝑛 = 2𝑘 + 1

• 𝑥𝑛 =

1,

(𝑥𝑘)2,

𝑥 ∙ (𝑥𝑘)2,

𝑛 = 0𝑛 = 2𝑘

𝑛 = 2𝑘 + 1

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 interclasare

Rezolvare:

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