Curs 8.
Metoda „DIVIDE ET IMPERA”
(Metoda Divizarii)
*Metoda generala de construire a algoritmilor, ce separa problema in doua sau
mai multe subprobleme de aceeasi natura cu problema initiala, dar cu
dimensiune mai mica. Descompunerea se face recursiv pana se ajunge la
probleme ce admit rezolvare imediata.
a=(a1,...| ...an)
a=(a1,..., ap......au, ...an)
m←
[ ]
p+u
2
Procedure DivImp (p,u,r) //p,u:indicii intre care se prelucreaza, r= rezultat
intors
{if (u-p)<ε then Prel(u,p,r)
Else {m←Intermediar(p,u)
DivImp(p,m,r1)
DivImp(m+1,u,r2)
Combin(r1,r2,r)
}
PP: DivImp(1,n).
Exemple.
[Link] a n elemente: {ai}i=1..n
ε =1; r←max(r1,r2)
function Max(i,j:int):int;
var a,b:int;
begin
if i=j then Max=v[i]
else {a=Max(i,(i+j) div 2
b=Max((i+j)div 2+1,j);
if (a>b) then Max=a
else Max=b}
end;
PP:Max(1,n); v=vectorul pt care se calculeaza maximul.
[Link] binara
Sa se gaseasca o valoare data intr-un vector sortat crescator.
a=(a1,...an) ↗
Cautam i cu ai=x (x dat).
-∞=a0<a1<...<an<an+1=∞
{ ( true ,i ) daca x=a
Rezultat : (b,i): pereche ( false ,i ) daca a < x i< a
i−1 i
Procedure Cautbin(p,u)
{ While p<=u
[ ]
p+u
{ i← 2 ;
Case x=ai: b←true; write (b,i); exit;
x<ai: u←i-1;
x>ai: p←i+1;
}
b←false; i←p;write(b,i);}
Complexitate: O(log n) (nu O(n))!: nu trebuie sa compare cu toate valorile din
vector, exploateaza faptul ca valorile sunt sortate crescator.
[Link] et Impera: Parcurgerea arborilor binari (inordine, preordine,
postordine).
[Link] prin insertie binara: O(n*logn)- cel mai bun timp posibil pentru
sortare (vezi Laborator 8).
[Link] TURNURILOR DIN HANOI
1 2 3
I.
Muta n discuri de pe tija 1 pe tija 2 respectand urmatoarele reguli:
La fiecare pas se muta cate un singur disc;
Nu este permis sa se aseze un disc cu diametrul mai mare peste un disc
cu diametrul mai mic.
Mutare (i,j): se muta discul din varful tijei i pe tija j.
H(n;i,j)= sirul de mutari necesare pentru a muta cele n discuri din varful tijei i
peste cele de pe tija j.
Exp. H(3;1,3)= mutarea a 3 discuri de pe 1 pe 3.
H(1;i,j)=(i,j)
H(n;i,j)=H(n-1;i,6-i-j) (i,j) H(n-1;6-i-j,j)
(6-i-j este a treia dintre tije, diferita de i si j)
1 2 3
II.
1 2
III.
H(3;1,2)=H(2;1,3) (1 2) H(2;3,2)=(1 2) (1 3) (2 3) (1 2) (3 1) (3 2) (1 2).
Hanoi(n; 1,2)
Procedure Hanoi(n;i,j)
Begin
If n=1 then write ( ‘(‘, i, ‘,’, j,’)’)
else {Hanoi(n-1,i,6-i-j);
Hanoi(1,i,j);
Hanoi(n-1,6-i-j,j)}
End.
6. Metoda de sortare Quicksort
Function Partition (a,lb,ub)
{pivot=a[lb]; start=lb; end=ub;
While(start<end)
{while a[start]<=pivot start++;
while a[end]>pivot end--;
if (start<end) swap(a[start], a[end]);}
swap(a[lb],a[end]); return end;}
Quicksort (a,lb,ub)
{if (lb<ub){
loc=Partition(a,lb,ub);
Quicksort(a,lb,loc-1);
Quicksort(a,loc+1,ub);}
PP...
Exemplu
4 20 15 5 7 2 1 19
11 8
start end
pivot
11 8 4 1 15 5 7 2 20 19
start
end
pivot
4 1 2 5 7 15 20 19
11 8
start end
pivot
start>end: STOP, interschimba pivotul cu elementul de pe pozitia end:
7 8 4 1 2 5 11 15 20 19
end start
7. Sortare prin interclasare (Mergesort)
Procedure Sort(p,u)
{If u-p<1 then
Else {m← 2 ; [ ]
p+u
Sort(p,m), Sort(m+1,u)
Interclasare (p,m,u)}}
i j
a: ap...am am+1...au
1
2
b k: pozitia din b pe care se scrie
Procedure Interclasare (p,m,u)
{i←p; j←m+1; k←p;
While i<=m && j<=u
{ If ai<aj then {bk←ai; i++;}
else {bk←aj; j++;}
k++;}
//i>m sau j>n:
If i>m then
for w=j to u do
{bk←aw; k++;}
else for w=i to m do
{bk←aw; k++;}
For i=p to u do ai←bi