Pagini recente » Atasamentele paginii Profil vldd | Monitorul de evaluare | Monitorul de evaluare | Monitorul de evaluare | Diferente pentru missing-numbers intre reviziile 3 si 4
Nu exista diferente intre titluri.
Diferente intre continut:
Reprezentarea grafica seamana cu litera greceasca <tex>\rho</tex>. Notam lungimea lantului cu <tex>\lambda</tex> si lungimea ciclului cu <tex>\mu</tex>.
!missing-numbers?missing_numbers_pic2.png!
== code(c) |
a = b = cap
repeta
a = a.next.next
b = a.next
cat timp (a!=b)
==
Cand <tex>a</tex> si <tex>b</tex> sunt amandoi in ciclu, <tex>a</tex> il va ajunge din nou pe <tex>b</tex>. Puteti vedea exact cum prin analiza cazurilor in care lungimea ciclului e para sau impara. In exemplul desenat, dupa sase iteratii cei doi pointeri vor indica acelasi element.
Pentru determinarea lungimii ciclului se mai poate face o parcurgere in care doar un pointer se misca. Acum dupa ce stim lungimea <tex>\mu</tex> a ciclului putem afla si lungimea <tex>\lambda</tex> a lantului astfel: luam un pointer la inceputul listei si al doilea care a facut deja <tex>\mu</tex> pasi in lista. Acum ii miscam pe cei doi cu aceeasi viteza. Dupa <tex>\lambda</tex> pasi cei doi pointeri vor fi egali. Astfel am obtinut o rezolvare liniara.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.