Probleme rezolvate2

Problema turnurilor din Hanoi

Se dau trei tije notate a, b, c si n discuri de diamtre diferite.
Initial, pe tija a se gasesc toate discurile pus in ordine crescatoare a diamtrelor lor (cel cu diametrul cel mai mare este pus la baza).
Sa se mute toate discurile de pe tija a pe tija b, folosind tija c ca tija intermediara, respectand urmatoarele conditii:
- de fiecare data se muta un singur disc
- un disc se poate pune numai deasupra unui disc cu diametru mai mare.

Daca avem un singur disc, mutam discul pe tija b si problema este rezolvata. (a->b)
Daca avem doua discuri: mutam primul disc pe tija c, al doilea disc pe tija b, apoi discul de pe tija c il mutam pe tija b.
(a->c,a->b,b->c)
Daca n>2 problema se complica, in sensul ca trebuie mult mai multe mutari de efectuat.
Pentru rezolvare vom folosi metoda Divide et impera.
Conform algoritmului general avem:
Imparte. Se descompune problema in 2 subprobleme: prima va contine n-1 discuri iar a doua un singur disc.
Stapaneste. Mutam cele n-1 discuri de pe tija a pe tija c folosind tija intermediara b prin apeluri succesive ale subprogramului recursiv.
Se muta discul ramas pe b, apoi se muta discurile de pe tija c pe tija b prin intermediul tijei a.
Combina. Combinarea solutiilor nu este necesara datorita faptului ca prin mutarea discurilor se realizeaza si secventa de rezolvare a problemei initiale.

functia muta are structura:

muta(numar discuri,de pe discul, pe discul,prin intermediul discului)

 var n:byte;
procedure muta(n:byte;a,b,c:char);{muta n discuri de pe a pe b prin intermediul tijei c}
begin
if(n=1)then writeln(a,'->',b) {mutam discul ramas pe tija a pe tija b}
            else begin
            muta(n-1,a,c,b);{mutam n-1 discuri de pe a pe c prin intermediul tijei b}
            writeln(a,'->',b);{mutam discul ramas pe tija a pe dija b}
            mutaxx(n-1,c,b,a);{mutam cele n-1 discuri de pe tija c pe tija b prin intermediul tijei a }
            end;
end;
begin
write('n=');readln(n);
muta(n,'a','b','c');{mutam n discuri de pe tija a pe tija b prin intermediul tijei c; a,b,c sunt numele discurilor}
end.