Turnurile din Hanoi - Partea Teoretică a unui Proiect
Turnurile din Hanoi reprezintă o problemă clasică de algoritmică și teoria jocurilor, care poate fi folosită pentru a demonstra concepte fundamentale în domeniul rezolvării problemelor recursive și al optimizării. În această parte teoretică, vom analiza problema Turnurilor din Hanoi din perspectiva teoretică și vom explora principalele sale caracteristici.
1.Descrierea Problemei
Problema Turnurilor din Hanoi constă într-un set de trei tije (sau coloane) și un număr de discuri de dimensiuni diferite, plasate pe una dintre tije. Scopul este de a muta toate discurile de pe prima tijă (sau coloană) pe a treia tijă, respectând următoarele reguli:
- Un singur disc poate fi mutat într-un moment dat.
- Fiecare disc trebuie să fie plasat pe o tijă în așa fel încât niciun disc mai mare să nu stea pe unul mai mic.
- La fiecare pas, un disc poate fi mutat doar de pe partea de sus a unei coloane.
2. Algoritmul de Rezolvare - Recursivitate
Problema Turnurilor din Hanoi este un exemplu clasic de problemă recursivă. Algoritmul de rezolvare se bazează pe ideea de a muta n-1 discuri de pe prima tijă pe a doua tijă, lăsând discul cel mai mare pe prima tijă, iar apoi mutând discul cel mai mare pe a treia tijă. După aceasta, se mută cele n-1 discuri de pe a doua tijă pe a treia tijă.
Recursivitatea este esențială pentru soluționarea problemei. Algoritmul poate fi descris astfel:
- Dacă există un singur disc, mută-l de pe prima tijă pe a treia tijă.
- Dacă sunt mai multe discuri, mută n-1 discuri de pe prima tijă pe a doua tijă, apoi mută discul cel mai mare pe a treia tijă, și în final mută n-1 discuri de pe a doua tijă pe a treia tijă.
3. Complexitatea Problemei
Numărul minim de mișcări necesare pentru a rezolva problema Turnurilor din Hanoi cu nn discuri este dat de formula recursivă:
T(n)=2n−1T(n) = 2^n - 1
Aceasta înseamnă că pentru fiecare disc adăugat la problemă, numărul de mutări necesare crește exponențial. De exemplu, pentru 3 discuri, numărul minim de mutări este:
T(3)=23−1=7T(3) = 2^3 - 1 = 7
Aceasta este o problemă NP-completă din perspectiva complexității algoritmice, întrucât necesită o cantitate semnificativă de calcule pentru un număr mare de discuri.
4. Exemple de Implementare
Algoritmul de rezolvare al Turnurilor din Hanoi poate fi implementat în diferite limbaje de programare. O implementare simplă, de exemplu, în Python ar putea arăta astfel:
def turnuri_hanoi(n, sursa, destinatie, intermediar):
if n == 1:
print(f"Mută discul 1 de la {sursa} la {destinatie}")
else:
turnuri_hanoi(n-1, sursa, intermediar, destinatie)
