Turnurile din Hanoi

Puzzle-ul "Turnurile din Hanoi" este cunoscut inca din antichitate iar rezolvarea lui computerizata este un exemplu clasic al folosiri tehnici "Dezbina si stapaneste" sau "Divide et impera".

Inainte de toate insa sa vedem in ce consta puzzle-ul.

Se dau trei tije, sa le numim, in aceasta ordine, A, B si C, si N discuri de marimi diferite ca in imagine. Scopul jocului este sa mutam toate discurile de pe tija A pe tija B folosind ca tija de "manevra" tija C. Pare simplu insa se mai adauga o regula: putem muta un disc de pe orice tija pe oricare alta cu o singura conditie, nu avem voie sa punem un disc cu diametrul mai mare peste unul cu diametrul mai mic. Puteti sa incercati acest joc pentru a va familiariza cu acest sistem.

O rezolvare informatica este una foarte simpla si sistematica:

1. Cazul elementar: Daca avem de mutat un singur disc de pe tija A pe tija B, pur si simplu il mutam.
2. Al doilea caz elementar: Daca avem de mutat doua discuri de pe tija A pe tija B: Mutam discul cel mic de pe tija A pe tija C, mutam discul mare de pe tija A pe tija B, mutam discul mic de pe tija C pe tija B. (putem scrie condensat AC AB CB)
3. Cazul general cu N discuri: mutam N-1 discuri de pe tija A pe tija C, mutam ultimul disc pe dija B si mutam din nou celelalte N-1 discuri de pe tija C pe tija C. Acum, pentru a le muta pe cele N-1 discuri de pe tija A pe tija C, N-1 devine un nou N, pe care il vom nota cu T.  Acum avem de mutat T discuri de pe tija A pe tija C, de data aceasta tija auxiliara va fi B. Deci, mutam T-1 discuri de pe tija A pe tija B, mutam  un singur disc de pe tija A pe tija C si mutam din nou T-1 discuri de pe tija B pe tija C. Pentru a face acest lucru T-1 devine un nou N ...
4. Se observa ca la cazul 3 avem un algoritm recursiv care va functiona pana cand se va ajunge la un caz elementar.

O schema a acestui program recursiv este:

f(A,B,C,N) = AB, daca N=1

                      AC

                      AB, daca N=2

                      CA

                      f(A,C,B,N-1)

                      AB , daca N=3

                      f(C,B,A,N-1)