Prezentarea algoritmului rezolvarii b2f22fi

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:
4la fiecare pas se muta un singur disc;
4un 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 AaB(mut discul de pe A pe B);
4daca n=2,atunci sirul mutarilor este : AaC,AaB,CaB;
4daca n>2 procedam astfel :
-mut (n-1)discuri AaC;
-mut un disc AaB ;
-mut cele (n-1)discuri CaB.

Observam ca problema initiala se descompune in trei subprobleme mai simple ,similare problemei initiale: mut (n-1)discuri AaC ,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 AaB 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,’a’,b) else begin hanoi(n-1,a,c,b);
writeln(a,’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.