| || 15 ||Feb
|| 18 ||Feb
|| 22-33 ||Feb
|| 29-30 ||Feb
|| 03 ||Mar
Click here for the class-sponsored design
Iteration is another technique for repetitive computations.
In this lab, you will use recursion to draw a circle and iteration
to throw darts at the circle, which is circumscribed in a square.
By the end of this lab, you should
This lab contains two parts, design
and implementation, due as shown at the beginning of this document.
The Monday after your design is due, a sample design will be handed out
in class. We may choose one of your designs for this honor; or, we may
write one up on our own. Remember, there is no right or wrong
design, but each design may have its own strengths and weaknesses.
- Gain more experience in API design
- Gain more experience with recursive solutions and programs
- Gain experience with iterative solutions and programs
- Understand how straight lines approximate curves in graphics
- Understand the role of randomness in simulations
[[[ Download PC zip ]]]
Read over this entire document before you start.
- Make sure you understand what is expected from you by way of an API.
- Study the recursion and interation examples given in class.
- If you need help, please ask.
Recall that the following lines should appear at the top of
any files that use the
Problem description: Slices of PI
Design and implement the class
does the following.
- Initially (when the constructor is called),
a square of size S is drawn. Also, fully contained in this
square, a circle of diameter S is drawn. The circle is actually
drawn as a sequence of n straight lines, where n is
a parameter of your constructor (hint, hint). In other words, a polygon
with n sides approximates the circle.
You must use recursion to draw the polygon.
- Subsequently, when a method of your choosing (in your design) is
- m darts are thrown at the circle in the square.
Based on the number that land in vs. out of the circle, you are to
return an approximation for PI as described below.
You must use iteration to throw the darts.
- The location of each dart throw is shown on the screen by a dot
(hint: a very small line). Red dots are those that land in the circle,
and black dots are those that land outside.
- Your design should include the specification
of some methods to find out how much work your
PI class did. At the least, methods to obtain the
following should be specified:
- How many darts were thrown?
- How many darts landed inside the circle?
- How many darts landed outside the circle?
- The results of these statistics should be formatted nicely as
a string of your
- Complete a design cover sheet.
- Define your
PI class. Give its API and
describe what all of its methods do.
If necessary, review the definition of an API from the Lab 4
- Don't worry yet about how your methods will do their work;
worry only about the API.
Monte Carlo methods and PI
Algorithms that involve randomness are often said to use Monte Carlo
technqiues---the term is named after the famous casino. Randomness is
often employed to lend a sense of realism to games and other simulations.
In this case, we wish to throw darts at a board. The board is square,
with each side having length S. How do we simulate a random
dart throw? Unlike real life, we do want to be sure that it lands
somewhere in the square. We can decompose the problem
into picking an x and a y coordinate, each chosen
randomly so that the dart lands in the square.
For example, if
we say the square is addressed from (0,0) to (S-1,S-1), then we can
int randX = (int) (Math.random() * S);
int randY = (int) (Math.random() * S);
to obtain a random x and y coordinate.
Next, we care whether the dart lands inside the circle. By this,
we mean that the distance of the dart from the center of the circle is
no greater than the circle's radius.
Why do we care? If we throw darts randomly at the square, some will
land in the circle, and some will land outside the circle. If the darts
are thrown uniformly, without bias, then we expect the darts to land in
the circle at a rate proportional to the circle's area with respect
to the square.
The circle's area is
___ ___ 2
circle area = PI x | S |
| --- |
| 2 |
while the square's area is
square area = S
Dividing these two yields the probability of a dart landing in the
circle, namely PI/4. Thus, if we throw darts, counting the number
that land inside the circle and the number that we throw, the ratio
of those two numbers should approach PI/4.
Looking forward to implementation
( class-sponsored design)
- Implement the PI problem.
- Complete a code cover sheet.
- Provide printouts of any files you created or modified for this
- Provide transcripts of your runs showing the required
statistics (as computed by your program, not by you!).
Last modified 09:31:43 CST 18 February 2000
by Ron K. Cytron