PROBLEMA TURNURILOR DIN HANOI

Prezentarea algoritmului rezolvarii

36575ktb68fnv2b 36575ktb68fnv2b 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 .

36575ktb68fnv2b Rezolvarea acestei probleme se bazeaza pe urmatoarele considerente logice :

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

36575ktb68fnv2b 4daca n=2,atunci sirul mutarilor este : AàC,AàB,CàB;

36575ktb68fnv2b 4daca n>2 procedam astfel :

36575ktb68fnv2b 36575ktb68fnv2b -mut (n-1)discuri AàC;

36575ktb68fnv2b 36575ktb68fnv2b -mut un disc AàB ;

36575ktb68fnv2b 36575ktb68fnv2b -mut cele (n-1)discuri CàB.

36575ktb68fnv2b

36575ktb68fnv2b 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 36575ktb68fnv2b 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.

36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b

PENTRU 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b

36575ktb68fnv2b n=1 AàB

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

36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b

36575ktb68fnv2b program turnurile _hanoi;

36575ktb68fnv2b 36575ktb68fnv2b var n:byte;

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

36575ktb68fnv2b 36575ktb68fnv2b begin

36575ktb68fnv2b 36575ktb68fnv2b if n=1 then writeln(a,’à’,b)

36575ktb68fnv2b 36575ktb68fnv2b else begin

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

36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b writeln(a,’à’,b);

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

36575ktb68fnv2b 36575ktb68fnv2b 36575ktb68fnv2b end;

36575ktb68fnv2b 36575ktb68fnv2b end;

36575ktb68fnv2b 36575ktb68fnv2b begin

36575ktb68fnv2b 36575ktb68fnv2b write(‘nr discuri pe tija A =’);readln(n);

36575ktb68fnv2b 36575ktb68fnv2b writeln(‘mutarile sunt urmatoarele :’);

36575ktb68fnv2b 36575ktb68fnv2b hanoi(n,’A’,’B’,’C’);

36575ktb68fnv2b 36575ktb68fnv2b readln;readln;

36575ktb68fnv2b 36575ktb68fnv2b end.