CPSC 170 Lab 6: More Recursion and Inheritance

As usual, create a lab6 subdirectory for today's lab, open this document in Netscape, and start emacs.

Sierpinski Triangles

A Sierpinski triangle is a geometric figure that may be constructed as follows:

Draw a triangle.
Draw a new triangle by connecting the midpoints of the three sides of your original triangle. This should split your triangle into four smaller triangles, one in the center and three around the outside.
Repeat (2) for each of the outside triangles (not the center one). Each of them will split into four yet smaller triangles. Repeat for each of their outside triangles.. and for each of the new ones.. and so on, forever. Draw a few rounds of this on paper to see how it works, then check out the demo to see it on screen.

Your job is to write an applet that draws a Sierpinski triangle. Think about the following:

A Sierpinski triangle is a recursively defined structure, since each of the three outer triangles formed by joining the midpoints is itself a Sierpinski triangle.
In practice you don't want to go on with the process "forever" as suggested above, so we'll limit how deep it goes. Define the depth of a Sierpinski triangle as the number of directly nested triangles at the deepest point. So a Sierpinski triangle consisting of a single triangle has depth 0; when a triangle is drawn inside of it, the resulting Sierpinski triangle has depth 1; when the three outside triangles have triangles drawn inside of them, the resulting triangle is depth 2, and so on. A depth of 10 or 11 gives a nice looking triangle in a reasonable amount of time. (The demo uses depth 10.) Smaller depths are interesting in that you can see more of the construction; higher depths generally take too long for casual viewing.
A triangle is a polygon, so you'll use the drawPolygon method. Remember that it takes an array containing the x coordinates, an array containing the y coordinates, and an integer indicating how many points should be drawn (3 for a triangle). Refer to pages 306-308 to refresh your memory on this.
Your initial triangle should look like the one in the demo -- one point at the top center of the applet and one point in each lower corner.
Your overall program is quite simple. The paint method will just call a recursive method sierpinski, passing it the Graphics object, the points of the initial triangle to be drawn, and the initial depth (0). Make the variables that hold the initial points instance variables and initialize them in the init method. The sierpinski method will then check to see if the desired depth has been exceeded (the depth can be a constant), and if not, draw the triangle, then call itself recursively to drawn the three Sierpinski triangles that will be embedded. Note that it will have to figure out what points to pass to each of these, and that each recursive call increases the depth by one.

When this works (that is, when your triangle looks like the one in the demo), modify it so that when the user clicks a new, random Sierpinski triangle is drawn. (The demo does this too.) This just means choosing three random points and repainting -- nothing will change in your paint or sierpinski methods (if you followed the guidelines above). For fun you can choose a random color each time as well, as the demo does.

Print your Sierpinski program.

Writing a Test

In this exercise you will use inheritance to read, store, and print questions for a test. First, write a class TestQuestion that contains the following:

a String variable that holds the test question
an abstract method to read the question (protected abstract void readQuestion())
an abstract method to return a string containing the question Now define two subclasses of TestQuestion, Essay and MultChoice. Essay will not need any additional variables, and it will implement the read and toString methods trivially. MultChoice, however, will need to store four choices along with the main question, so it will need extra variables to hold these. (Assume there are always exactly four choices.) It will also need to read these in and return them as part of its string.
Now define a class WriteTest that creates an array of 10 TestQuestion objects. It should read the questions from the standard input as follows: First, it reads a character. If the char is 'm', the next question is multiple choice; it it's 'e', the question is essay. Then it reads the question, then repeats for 10 questions. When it reads a mult choice question, it should create a mult choice object; when it reads an essay question, it should create an essay object. Either way, the object should be stored in the array after its info is read. When all of the data has been read, use a loop to print the questions, numbered, in order, and there's your test! Use the data in testbank.dat to test your program.
HAND IN:
- Hand in hardcopy of Sierpinski.java, WriteTest.java, TestQuestion.java, Essay.java, and MultChoice.java.
- Tar the files in your lab6 directory and email the .tgz file to me (bloss@cs.roanoke.edu).

CPSC 170 Lab 6: More Recursion and Inheritance

Sierpinski Triangles

Writing a Test

HAND IN: