Description
In class, we looked at the Tower of Hanoi puzzle, its recurrence relationship, and a recursive version of the algorithm based on that relationship. The Tower of Hanoi is an example of a Divide and Conquer algorithm that divides by the constant 1 (i.e. each half of the problem is size n-1).
The Wikipedia article on the Tower of Hanoi describes the following iterative version of the algorithm:
For an even number of disks:
make the legal move between pegs A and B (in either direction)
make the legal move between pegs A and C (in either direction)
make the legal move between pegs B and C (in either direction)
repeat steps 1-3 until complete
For an odd number of disks:
make the legal move between pegs A and C (in either direction)
make the legal move between pegs A and B (in either direction)
make the legal move between pegs B and C (in either direction)
make the legal move between pegs A and C (in either direction)
repeat steps 1-3 until complete
The “in either direction” provision requires determining whether moving the disk from peg A to C or from C to A is the legal move.
The assignment is to implement this iterative algorithm as hanoi(int ndisks, int src, int dest) in either C++ or Java. The function uses an array of three integer stacks to represent the poles, and small integers between 1 and ndisks to represent the disks, with the largest disk numbered 1 and the smallest as ndisks.
Also create a local supporting function moveDisk() that takes the pole array and the src and dest pole indexes. The function determines the move direction by comparing the top disks on the indexed stacks, then moves the disk and prints a message “Move disk from pole %d to pole %d\n” to standard out.
The algorithm is complete when all ndisks disks have been moved to the dest pole. In implementing this algorithm, consider what kind of initialization could be done to simplify the manipulation of the stacks in moveDisk().
Put your code in a file named “HanoiStack.cpp” or “HanoiStack.java” and provide a main program that calls hanoi() to move 1, 2, 3, and 4 disks from pole 0 to pole 2. Ensure that the correct steps are printed to standard ouput for each case.
