CIS 501
Spring, 2003

Assignment Number 06 - Towers of Hanoi Recursion

Reading: Begin the readings for Section G in the Syllabus.

Programming: Two parts - both to be done individually.

Part 1: This part of the assignment is to be written out by hand and is to be done individually.

Let n be the height of a tower to be moved from one tower to another and consider the Towers of Hanoi algorithm written as follows: 

	void move_tower (n, from_tower, to_tower, aux_tower)
	{   
           if (n > 0) {
              move_tower (n-1, from_tower, aux_tower, to_tower);
              move_one_disk (from_tower, to_tower);
              move_tower (n-1, aux_tower, to_tower, from_tower);
           }
	}

If n = 3, the from_tower is t1, and the to_tower is t3, the initial steps of a trace of this function might read as follows: 

         move_tower (3, t1, t3, t2)

            1. move_tower (2, t1, t2, t3)
	    2. move_one_disk (t1, t3)
            3. Move_tower (2, t2, t3, t1

		1.1 move_tower (1, t1, t3, t2)
		1.2 move_one_disk (t1, t2)
		1.3 move_tower (1, ??, ??, ??)

Your job is to complete the trace of the execution of this algorithm, including the designation of steps 1.1.1, 1.1.2, 1.1.3, 3.1, 3.2, 3.3 etc., etc., etc. Remember that the algorithm continues to recurse until n=0, at which point, finally, one disk is moved.

Part 2: This assignment is to be programmed and is to be done individually.

Using the algorithm given in Part 1, write a C++ program, with appropriate functions, to produce output similar to (but much better than) that shown on the next page. (In other words, your output should show a complete tabular trace of the execution of the program along with a reasonably nice graphics display of the movement of the disks on the towers.

Due: To be determined.