towers of hanoi

1. TOWERS OF HANOI

2. •Move: A  B
•For, N=1, the only move is AC
•For, N=2, the moves are AB, AC, BC
• For, N=3 ?

5. •For N=N: following steps are used:
1.Move top n-1 disks from A to B
2.Move top disk from A to C
3.Move top n-1 disks from B to C (recursion by changing the B and C)

6. Algorithm
•General Notation of Algorithm is: TOWER (N, BEG, AUX, END)
•EXAMPLE MOVE: TOWER(1, BEG, AUX, END) I.E, BEGEND
•Steps for N disks:
•1. TOWER(N-1, BEG,END,AUX)
•2 TOWER(1, BEG,AUX,END)
•3 TOWER(N-1, AUX,BEG,END) --- (recursion)
•Example : TOWER(4,A,B,C)

8. •TOWER(N,BEG,AUX,END)
•1 If N=1, then
• (a) Write : BEGEND
• (b) Return
•2 [Move N-1 disks from BEG to AUX]
• Call TOWER(N-1,BEG,END,AUX)
•3 Write: BEGEND
•4 [Move N-1 disks from AUX to END]
• Call TOWER(N-1,AUX,BEG,END)
•5 Return