Tuesday, December 1, 2009

SECTION 005: Lab test 03

The Towers of Hanoi is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following rules:

1. Only one disk may be moved at a time.

2. Each move consists of taking the upper disk from one of the rods and sliding it onto another rod, on top of the other disks that may already be present on that rod.

3. No disk may be placed on top of a smaller disk.

Below you will find a partial implementation of a Tower of Hanoi with two methods missing: getHeight and hanoi. For this test you will implement these methods.

--- the start Pole, destination Pole and the intermediate Pole are labeled A, B, C.

--- Each disk is labeled (from 1 to the n, n is the height of the tower)

--- Disk 1 is the smallest disk, and Disk n is the largest one.

Hint : The idea is that the method of moving n disks from start pole to destination pole is the same as the method of moving n-1 disks. For example, initially the tower has height 5, we must recursively move a tower of height 4 from A to C, move the biggest disk 5 from A to B (by simply calling method moveDisk), and finally recursively move the tower of height 4 to B from C.

public class HanoiTower {
static int moves = 0;  //number of moves so far

/*Method getHeight is used to get the height of tower from user input*/
static int getHeight()
   // TO DO

/*Method hanoi moves the tower of height n recursively
 * it accept four arguments: the height of the current tower n, the fromPole, the toPole and the withPole.
 * @param n the height of the current tower
 * @param fromPole the start pole
 * @param toPole the destination pole
 * @param withPole the intermediate pole
 * */
static void hanoi(int n, char  fromPole, char  toPole, char  withPole)
   // TO DO

/*Method moveDisk move the disk of diskLabel by simply printing on the console each move*/
static void moveDisk(int diskLabel, char fromPole, char toPole)
     System.out.println("steps: "+ moves);
     System.out.println("Move " + diskLabel + " from " + fromPole + " to " +toPole);

 * @param args
public static void main(String[] args) {
    // TODO Auto-generated method stub

    int TowerHeight;
    char FromPole='A', ToPole='B', WithPole='C';

    System.out.println("Please Enter Tower height...");

    TowerHeight = getHeight();

    hanoi(TowerHeight, FromPole, ToPole, WithPole);



Here is the output of height of 3 after you properly implement the methods:

Please Enter Tower height...


steps: 1

Move 1 from A to B

steps: 2

Move 2 from A to C

steps: 3

Move 1 from B to C

steps: 4

Move 3 from A to B

steps: 5

Move 1 from C to A

steps: 6

Move 2 from C to B

steps: 7

Move 1 from A to B


Submit your HanoiTower.java file to espiggy@gmail.com before 4:00pm. No late submission accepted!

No comments: