CIS 068
Fall, 2002

Assignment 6h-F2002: Hints for Towers of Hanoi

Revision 4 (August 08, 2002)
PAGE UNDER REPAIR AS OF 8-9-02

PART I

One of your colleagues pointed out a potentially confusing aspect of Assignment 6. They suggested that there was no sequence of steps 1.1.1, 1.1.2, 1.1.3 etc. if you use the test

            if (n> 1)

in the Towers function.

If you trace this carefully, however, you will notice that there IS a 1.1.1 but it is a single step involving the calling of and immediate exit from the function, so it actually does nothing. Something similar happens in step 1.3.1.

Then of course, there are steps 3.1, 3.2, 3.3 etc that you must finish. This work is not excrutiating -- it should not take you long to do. But, as you proceed, even through the steps I gave you, DRAW a PICTURE as needed.

PART II

Outside my office is a three-page sample output that your program should produce -- unless, of course, you would like to produce something even more gorgeous. This was produced using an algorithm that had a stopping state of n > 0 which is what I suggest you should use.

The trick is to figure out where to put your output statements.

Here are a few hints.

  1. Let the user type in n but don't try this for n>5.
  2. MoveOneDisk should be a separate function.
  3. Modelling the towers -- Treat each tower as an ADT (call it tower_type) that behaves like a stack. In point of fact, just to show that reuse has its place, go back and review the material on stacks in the text (pp. 187 - 192). Read this material carefully and then use it to define your own class tower_type which is identical to stack_type except that ItemType (as shown in the book) will be the base type char for your class.

    NOTE: If you are really ambitious, you could copy, with but one change (see below), the entire stack class template shown on pp. 193-197. In this case, your main program would contain the code                 type_def StackType<char> tower_type;

    Regardless of whether you
    1. create your own tower_type;
    2. use the material on pp. 187-192 to help you create tower_type; or
    3. copy, character for character, the material on pp. 193-197 and use the above line of code to create tower_type
    you will in the end need to include in your main program a statement like

                    tower_type my_towers[3];

    to declare (create an instance of) your three towers (as an array). To make it easy to print your towers across a page, declare tower_type and my_towers as being global to your program (something I will probably never tell you to do again). When you write the code to display the three towers in parallel, you will not need to pass any arguments to this display function -- just let it print the contents of the three towers (see below).

    Note that the top of stack pointer, top, in the stack_class has the same behavior as your tower height variable (except that the actual tower height is always one greater than the top of stack pointer.. Furthermore, items[MAX_ITEMS] behaves like the tower of disks that your are modeling.
  1. Just to complete this hint, your move_one_disk function would now appear in the main program and it would look something like this (assuming you use try and catch as shown in the book) --

        void move_one_disk (from, to)
        {
            char one_disk;
            my_towers[from].pop(one_disk);
            my_towers[to].push(one_disk);
        }
     

  2. Finally, note that to display your towers, you may need two additional functions in your tower_type class, namely a) a function that returns the height of a tower, and b) a function that returns the character representing a disk at position i of a tower (this function allows us to peek at characters at and below the top without popping any characters).

    Your display function can be in the main program. Remember that to display the towers, find tallest, the height of the tallest tower, and write a loop that runs from tallest down to 1 printing out those disks that are listed as being on each of the towers. You should use a lookup table to lookup each letter (a char type) listed as being on a tower and find the string you wish to use to represent that letter as a disk on your towers. For example, you might choose the following crude characters for the string to represent the disks B, D, or F: 

    BggyggB
DggggyggggD
FggggggyggggggF

    Hints: Include the blank in your lookup table, simply arranged as the character

    y

    Note that you still need to figure out how to align the posts in your towers. You might consider adding two fields to your lookup table, one for each disk including the blank. Both fields would be of type int. The first would contain the number of blanks needed at the start of a line in order to properly align the posts for Tower 1. The second int would be the number of blanks needed in the middle of a line in order to properly align the posts in Tower 2 and Tower 3. In the end, your table might have four fields as illustrated below for several entries. To keep the output to 80 characters in length let's limit the number of disks to 10, not 15. If I made any counting mistakes, you will need to correct them. 

    Key     Representation	         Lead Blanks Mid Blanks
' '	y			 11          27
'B'	BgygB			  9	     23
'D'	DgggygggD	 	  7	     19
'F'	FgggggygggggF		  5	     12
'K'     KggggggggggyggggggggggK	  0           5
  3. READING: Chapter 7, Sections …

    4. 7.1
    7.2 Pay particular attention to the recursive definition of n!
    7.3 Study Table 7.1 and the little box below it (p. 397)
    7.4
    7.5
    7.7 (SKIP 7.6)
    7.8
    7.10 (SKIP 7.9)
    7.12 (SKIP 7.11)
    NOTE: You will two fundamentally different kinds of recursion. One is a more mathematically oriented recursion (like the factorial) that returns a value as is called as part of an expression in a C++ code line. The other is a void function that operates on some data structure such as the three Towers of Hanoi.
     

  4. QUESTIONS:
    • How many moves are needed to move 2 disks from tower1 to tower3?
    • How many moves are needed to move 3 disks from tower1 to tower3?
    • In general, how many moves are needed to move n disks from tower1 to tower3?

    1. Treat each tower as an ADT (call it tower_type) that behaves like a stack. In point of fact, just to show that reuse has its place, go back and review the material on stacks in the text (pp. 187 - 192). Read this material carefully and then use it to define your own class tower_type which is identical to stack_type except that ItemType (as shown in the book) will be the base type char for your class.

      NOTE: If you are really ambitious, you could copy, with but one change (see below), the entire stack class template shown on pp. 193-197. In this case, your main program would contain the code

                  type_def StackType<char> tower_type;

      Regardless of whether you
          d. create your own tower_type;
          e. use the material on pp. 187-192 to help you create tower_type; or
          f. copy, character for character, the material on pp. 193-197 and use the above line of code to create tower_type

      you will in the end need to include in your main program a statement like

                  tower_type my_towers[3];

      to declare (create an instance of) your three towers (as an array).

      Note that the top of stack pointer, top, in the stack_class has the same behavior as your tower height variable. Furthermore, items[MAX_ITEMS] behaves like the tower of disks that your are modeling.

    2. Just to complete this hint, your move_one_disk function would now appear in the main program and it would look something like this (assuming you use try and catch as shown in the book) -- 
      BggyggB
DggggyggggD
FggggggyggggggF
    3. Finally, note that to display your towers, you may need two additional functions in your tower_type class, namely a) a function that returns the character representing a disk to be printed at height h of a tower. Note that if h is bigger that the current height of your tower this function should return a blank.

    Your display function can be in the main program. Remember that to display the towers, find tallest, the height of the tallest tower, and write a loop that runs from tallest down to 1 printing out those disks that are listed as being on each of the towers. You will have nested loops and you should us a lookup table to lookup each letter (a char type) on a disk and find the string you wish to use to represent that letter as a disk on your towers. For example, you might choose the following crude characters for the string to represent the disks B, D, or F:

    Bg g y g g B

    Dg g g g y g g g g D

    Fg g g g g g y g g g g g g F

    Hints: Include the blank in your lookup table simply arranged as the character

    y

    Note that you still need to figure out how to align the posts in your towers. You might consider adding two fields to your lookup table, one for each disk including the blank. Both fields would be of type int. The first would contain the number of blanks needed at the start of a line in order to properly align the posts for Tower 1. The second int would be the number of blanks needed in the middle of a line in order to properly align the posts in Tower 2 and Tower 3. In the end, your table might have four fields as illustrated below for several entries. To keep the output to 80 characters in length let's limit the number of disks to 10, not 15. If I made any counting mistakes, you will need to correct them. 

    Key     Representation           Lead Blanks Mid Blanks
' '     y                        11          27
'B'     BgygB                     9          23
'D'     DgggygggD                 7          19
'F'     FgggggygggggF             5          12
'K'     KggggggggggyggggggggggK   0           5

    Still have questions? Come to class on Monday.