ID #123 · Colecția InfoAs · Operatori și expresii

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`