PROBLEMA TURNURILOR DIN HANOI, Prezentarea algoritmului rezolvarii

PROBLEMA TURNURILOR DIN HANOI

Prezentarea algoritmului rezolvarii

Fie trei tije verticale notate A,B,C .Pe tija A se gasesc asezate n discuri de diametre diferite ,in ordinea crescatoare a diametrelor,privind de sus in jos . Initial ,tijele B si C sunt goale .Sa se afiseze toate mutarile prin care discurile de pe tija A se muta pe tija B , in aceeasi ordine ,folosind ca tija de manevra C si resspectand urmatoarele reguli:

la fiecare pas se muta un singur disc;

un disc se poate aseza numai peste un disc cu diametrul mai mare .

Rezolvarea acestei probleme se bazeaza pe urmatoarele considerente logice :

-daca n=1 ,atunci mutarea este immediata A B(mut discul de pe A pe B);          

daca n=2,atunci sirul mutarilor este : A C,A B,C B;

daca n>2 procedam astfel :

-mut (n-1)discuri A C;

-mut un disc A B ;

-mut cele (n-1)discuri C B.

Observam ca problema initiala se descompune in trei subprobleme mai simple ,similare problemei initiale: mut (n-1)discuri A C ,mut ultimul disc pe B ,mut cele (n-1)discuri C-->B.Dimensiunile acestor subprobleme sunt : n-1,1,n-1.

Aceste subprobleme sunt independente ,deoarece tijele initial (pe      care sunt dispuse discurile ),tijele finale si tijele intermediare sunt diferite.Notam H(n,A,B,C)=sirul mutarilor a n discuri de pe A pe B, folosind C.

PENTRU                                                               

n=1 A B

n>1 H(n,A,B,C)= H(n-1,A,C,B),AB, H(n-1,C,B,A)

program turnurile _hanoi;

var n:byte;

procedure hanoi(n:byte;a,b,c:char);

begin

if n=1 then writeln(a,' ',b)

else begin

hanoi(n-1,a,c,b);

writeln(a,' ',b);

hanoi(n-1,c,b,a);

end;

end;

begin

write('nr discuri pe tija A =');readln(n);

writeln('mutarile sunt urmatoarele :');

hanoi(n,'A','B','C');

readln;readln;

end.