Towers of Hanoi
-
Create a last-in-first-out (LIFO) data structure.
-
Write a program that will solve the Towers of Hanoi.
-
Solve the problem using both recursion and iteration.
-
Use stack data structures more extensively.
This assignment was heavily copied from the wonderfully competent faculty at Princeton University. Permission to use the assignment was granted via email by Dr. Robert Sedgewick. We gratefully acknowledge the material from Princeton University used in this assignment! The original Princeton assignment is here.
Copyright © 2000–2011, Robert Sedgewick and Kevin Wayne.
-
Create a new
Java
project calledP5
and importTowersOfHanoi-starter.jar
.
Your directory should look like this:
P5/ ├── resources │ └── Towers.jpg └── src ├── MyStack.java ├── MyStackTestProgram.java ├── UserInterface.java ├── TowersOfHanoi.java └── StdDraw.java
There are two parts to this assignment.
-
The first part is gaining a better understanding of how stacks work.
-
The second part is to understand how to implement the Towers of Hanoi algorithm.
You will be using a generic ArrayList
to create a stack and using the MyStackTestProgram
class to test your
implementation. The last index of the ArrayList
is the top of the stack.
Note
|
You may use any method in ArrayList except contains , indexOf , and lastIndexOf .
|
-
Open the
MyStack
class. -
Declare a private field of type
ArrayList<E>
-
Implement each method using the javadoc.
-
Start by implementing the
toString()
method since all of the tests in theMyStackTestProgram
class depend on this method being correct.
-
-
Remember to incrementally develop. Test one method at a time.
Warning
|
Your implementation of MyStack.java MUST pass all testing
in order to use it for this assignment.
|
-
Add code to the
main
method to initialize the puzzle by pushing all the discs onto the left stack, in descending order. Run the program with the command line arguments"10 -recursive"
and you should see the picture shown below.
Your program must meet the following specifications:
-
The code must produce the correct upload file and assertion messages.
-
Work on your own, as always.
-
You must submit
TowersOfHanoi.java
with the recursive and iterative solutions. -
Assignments should be implemented using Java 1.8.
-
Make sure your code runs on machines in the COMCS 120 lab.
-
Submit your program to the Checkin tab as you were shown in the recitation.
-
Read the syllabus for the late policy.
-
We will be checking programs for plagiarism, so please don’t copy from anyone else.
-
Assignments will be checked to make sure you implemented both recursive and iterative solutions.
-
100 points for perfect submission.
-
0 points for no submission, will not compile, submitted class file, etc.
-
Preliminary Tests:
-
testCompile: Checks compilation. (0 points)
-
testRecursive2: Checks recursive Tower of Hanoi solution, with 2 discs. (20 points)
-
testRecursive3: Checks recursive Tower of Hanoi solution, with 3 discs. (20 points)
-
testRecursive4: Checks recursive Tower of Hanoi solution, with 4 discs. (20 points)
-
testIterative: Checks iterative Tower of Hanoi solution, with 6 discs. (Extra Credit: 10 points)
-
-
Final Tests are identical to the preliminary tests, but with more discs.
-
testRecursive5: Checks recursive Tower of Hanoi solution, with 5 discs. (20 points)
-
testRecursive6: Checks recursive Tower of Hanoi solution, with 6 discs. (20 points)
-
Important
|
Submit TowersOfHanoi.java to Checkin |