curs05.txt

STRUCTURI DE DATE SI ALGORITMI

                                   Curs 5


Am vazut ca:	
Algoritmul recursiv si relatii de recurenta
Exemplu:Problema turnurilor din Hanoi
Se dau n discuri: a1, a2, ... , an de dimensiuni diferite, cu 
d1 < d2 < ... < dn , di  -  fiind diametrul discului. Discurile respective 
sunt stivuite pe o tija:

Se cere sa se deplaseze aceasta stiva pe o alta tija, folosind ca manevra o
tija auxiliara, respect僴du-se conditia << Un disc nu poate fi plasat dec僼
peste un disc mai mare >>.
Problema P(n) a deplasarii a n discuri, se rezolva prin deplasari succesive
ale discurilor de pe o tija pe alta. Deplasarea de pe o tija pe alta este echivalenta cu deplasarea a n-1 discuri de pe tija intiala
(ti) pe tija de manevra, apoi plasarea celui mai lung disc pe tija finala,
pentru ca la sf價sit sa se aduca de pe tija de manevra (tm), pe tija finala
(tf), cele n-1 discuri deplasate.
Primele miscari s-ar figura astfel:


Procedura Hanoi:

Hanoi(n, ti, tf, tm)
{
if(n=1) then muta (ti, tf) //deplaseaza discul superior 					 // de pe ti pe tf
else |  Hanoi(n-1, ti, tm, tf)
     |  muta(ti, tf)
     |_ Hanoi(n-1, tm, tf, ti)
}
Pentru o problema P(1) , timpul T(1) = 1 , pentru o mutare.
Pentru P(n) , timpul:
(1)
Dorim sa aflam ordinul de complexitate a lui T(n).
Asociem relatiei (1) ecuatia caracteristica: 



Fac僴d identificarea:	
Ordinul este O(2n), adica o complexitate exponentiala.
Relatii de recurenta. Clasele relatiilor de recurenta
1.f(n) = a鵩(n - 1) + b
 x0 = a鵻0 + b
Prin scaderea celor doua relatii, rezulta un algoritm exponential cu baza a:
f(n) - x0 = a  (f(n-1) - x0)
2.f(n)=a鵩(n-1)+b鵩(n-2)
f(n) = t