## Tower of Hanoi :

Tower of Hanoi is puzzle in which there are 3 rods and discs if various sizes. In this we have to move discs of different sizes from one rod to another using following rules:

- Only one disk can be moved at a time.
- Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
- No disk may be placed on top of a smaller disk.

When there are n no. of discs then max no.of steps involved to solve the problem is 2^{n} – 1.

e.g. 4 discs involve 2^{4} – 1 = 15 steps

tower of hanoi |

.**ALGORIGTHM**:

To move *n* discs from peg A to peg C:

- move
*n*−1 discs from A to B. This leaves disc*n*alone on peg A - move disc
*n*from A to C - move
*n*−1 discs from B to C so they sit on disc*n*

The above is a recursive algorithm, to carry out steps 1 and 3, apply the same algorithm again for *n*−1. The entire procedure is a finite number of steps, since at some point the algorithm will be required for *n* = 1. This step, moving a single disc from peg A to peg C, is trivial.

__C SOURCE CODE:__

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
#include<stdio.h> #include<conio.h> void toh(int n, char from, char to, char aux) { if (n == 1) { printf("n Move disk 1 from rod %c to rod %c", from, to); } toh(n-1, from, aux, to); printf("n Move disk %d from rod %c to rod %c", n, from, to); toh(n-1, aux, to, from); } void main() { int n; printf("nEnter the no. of disks :"); scanf("%d",&n); printf("nSequence of steps are:n"); toh(n, 'A', 'C', 'B'); getch(); } |