Aplicatii „Divide et Impera

Report
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 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
A
B
C
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
Pentru n=12 şi vectorul 3,10,27,31,42,58,63,75,81,94,101,149
1
3
2
10
3
27
4
31
5
42
6
58
7
63
8
75
9
81
10
94
11
101
12
149
6
58
3
9
27
81
1
4
3
31
7
2
63
10
2
5
2
2
2
10
42
10
10
10
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*mn 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, sa 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.
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.
// Scrieti un program care sa rezolve
// cu metoda "Divide et Impera" ecuatia:
//
x^3-3*x+1=0
//Cautam solutiile in intervalele:
//[-2,-1],[0,1],[1,2]
#include<iostream>
#include<cmath>
using namespace std;
double f(double x)
{
return x*x*x-3*x+1;
}
double Sol(double a,double b)
{
double m=(a+b)/2;
if(fabs(b-a)<=0.0001) return m;
if(f(a)*f(m)<0) return Sol(a,m);
if(f(m)*f(b)<0) return Sol(m,b);
}
int main()
{
cout<<"Solutiile ecuatiei: x^3-3*x+1=0"<<endl;
cout<<"x1= "<<Sol(-2,-1)<<endl;
cout<<"x2= "<<Sol(0,1)<<endl;
cout<<"x3= "<<Sol(1,2)<<endl;
return 0;
}
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,
=0
(  )2 ,
•  =
 = 2
 ∙ (  )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

similar documents