Colecția InfoAs · Clasa a X-a Divide et Impera Probleme cu Divide et Impera
Problema Hanoi
Jocul turnului din Hanoi este un puzzle ce constă în găsirea soluției următoarei probleme. Avem trei tije, A, B și C. Inițial, pe tija A sunt amplasate n discuri de diametre variabile, în ordine descrescătoare a razei de la bază; celelalte două tije sunt goale (exact ca în figura de mai jos, cu n = 8 discuri).
Scopul jocului este de a muta toate discurile de pe tija A pe tija C (folosind ca tijă ajutătoare B), respectând regulile următoare:
- doar un singur disc poate fi mutat, la un moment dat;
- fiecare mutare constă în luarea celui mai de sus disc de pe o tijă și glisarea lui pe o altă tijă, chiar și deauspra altor discuri care sunt deja prezente pe acea tijă;
- un disc de rază mai mare nu poate fi poziționat deasupra unui disc mai mic.
Cerință
Se dă numărul natural n. Presupunând că pe tija A se află inițial n discuri amplasate corect, să se determine mutările necesare pentru ca toate discurile să fie mutate pe tija C, respectând regulile jocului.
Date de intrare
Programul citește de la tastatură numărul natural n, ce reprezintă numărul de discuri aflate pe tija A.
Date de ieșire
Programul afișează pe ecran mutările necesare pentru a rezolva corect problema. Mutările separate sunt plasate câte una pe linie și sunt notate astfel: SRC DEST (cu un spațiu între cele două) cu semnificația: mutăm un disc de pe tija SRC pe tija DEST (unde SRC și DEST pot avea valorile A, B sau C).
Restricții și precizări
1 ≤ n ≤ 15
Exemplu
2
A B A C B C
Explicația exemplului
Rezolvarea este cea din imagine:
Problemă adăugată pe InfoAs de 
cout << "Suma este " << s;