This program is a Recursion example problem. This is a pretty beginner class so

Question

This program is a Recursion example problem. This is a pretty beginner class so we haven’t discussed any major topics. We are using abstract methods and exception handling to deal with this problem/ arrays and other basic java topics binary object files.I will include an example as reference to how much we have used. Essentially this is an excersie on Recursion

Project 3: Tower(s) of Hanoi

We discussed the Tower of Hanoi problem in the classroom lecture on recursion, and is described in more detail in Chapter 11, Programming Project 7.

Legend says that this problem was originated either by Buddhist monks, Brahman priests, or the guardians of a Vietnamese temple, take your pick. In each case, they believed that if the puzzle could be solved using 64 disks, the world would end. Since the number of moves required to solve the Tower of Hanoi problem using “n” disks is 2n - 1, and assuming that each move would take roughly one second, then moving 64 disks from one peg to another would take almost 600 billion years to complete. (Astronomers tell us that universe as we know it today is no more than 14 billion years old, and the life of our sun is roughly 10 billion years, with 5 billion still to go.)

The most common algorithm to solve this problem involves multiple recursion. Here’s the pseudocode for such a method:

Invoke the method specifying these 4 parameters for this level of recursion:

1.n (the number of disks to move)

2.the from peg

3.the to peg

4.an intermediate peg as necessary

Base case: if n = 0, then just return (do nothing)

Recursive case:

Step 1: invoke method again (a new level of recursion) using parameters

1.n – 1 (the number of disks to move)

2.from the current from peg

3.to the current intermediate peg

4.using the current to peg as necessary

Step 2: move the nth peg from the current from peg to the current to peg

Step 3: invoke method again (a new level) using as parameters

1.n – 1 (the number of disks to move)

2.from the current intermediate peg

3.to the current to peg

4.using the current from peg as necessary

Write a method in Java that implements the above pseudocode. Show the moves required by adding a “print” statement in Step 2 of the recursive case showing the current from and to pegs.

Write a “tester” program to display the moves required when n = 3, n = 4, and n = 8 (input from the user?). To make things easy, label the initial from peg A, the initial intermediate peg B, and the initial to peg C.

Explanation / Answer

public class TowersOfHanoi {
public static void move(int n,String from,String to,String intermediate){
if(n==0){
return; //TERMINATION CONDITION
}else{
move(n-1,from,intermediate,to); //STEP 1
System.out.println("move 1 disc from " + from+" to "+to);//STEP 2
move(n-1,intermediate,to,from); //STEP 3
}
}
}

DRIVER PROGRAM:

public class TowersOfHanoiDriver {
public static void main(String[] args) {
System.out.println("for 3 disks");
TowersOfHanoi.move(3, "A", "B", "C");
System.out.println("for 4 disks");
TowersOfHanoi.move(4, "A", "B", "C");
System.out.println("for 8 disks");
TowersOfHanoi.move(8, "A", "B", "C");
}
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.