CS1500
Algorithms and Data Structures for Engineering, FALL 2012
LAB 3:Tower of Hanoi
Write a program that solves the Tower of Hanoi problem.
To begin with, you are given three towers named A, B and C. There are n
pegs (n is an input) placed on tower A, while towers B and C are empty.
The pegs are numbered 1 through n and pegs are placed in order. (Peg
numbered n is at the bottom, peg numbered n − 1 is on top of that, and
so on with peg numbered 1 being at the top.) Your task is to transfer
all the pegs from tower A to tower B.
The rules for peg transfer are the following:
- Only one peg transfer is allowed per step, from one tower (source) to another (destination).
- You must immediately place the peg that you take out of a tower on another tower. (This is a one step operation.)
- You can only take out the topmost peg of any tower.
- You can put a peg only at the top of a tower.
- No higher numbered peg should ever be above a lower numbered peg.
Write a program that takes n as input and prints out the sequence of
steps to perform to transfer n pegs from tower A to tower B. Each step
should be a move that tells which peg is being transferred from which
tower (source) to which tower (destination). Of course, each step
should be a valid step as per the above-mentioned rules.
For this
assignment, you are required to implement a recursive solution.