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:
- Cazul elementar: Daca avem de mutat un singur disc de pe tija A pe tija B, pur si simplu il mutam.
- 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)
- 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 ...
- 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)