C++ Homework for Week 5.
Be prepared to demonstrate this program
for your TA in your designated tutorial slot in week 6. (And yes I know that
there will be a quiz in week
6.)
This week's program uses an
ordered dictionary to support an n body simulation that goes by the name the
"Jumping Leprechauns".
(Note this
problem is from Data Structures
and Algorithms in Java 4th Edition ,
by Goodrich and Tamassia. )
The
simulation involves n leprechauns numbered from 0 ... n-1. Each leprechaun
possesses a bag of gold, with gi. Initially gi = 1000000 dollars for all i.
Each leprechaun stands at a location
xi, a double precision floating point value. Initially xi = i*gi.
One iteration of the
simulation processes the leprechauns from 0 ... n-1. Processing a leprechaun
moves (jumps) a leprechaun to a location xi + rgi, where r is a random number
between -1 ... 1. The leprechaun then steels half the gold from the nearest
leprechauns to its right and left, if he indeed has both neighbours. If the
position moved to is either the largest or smallest value of all xi, then there
is only one neighbour that is nearest. In this case he steals all of the gold
from the nearest leprechaun and the bankrupt leprechaun is out of the game. The
simulation ends when a single leprechaun is
left.
Write a program to
perform a sequence of iterations of this simulation for a given number of
leprechauns n. You should maintain the positions of the leprechauns in a binary
search tree. Your program should output the state of the simulation at the end
of every iteration, by printing xi and gi for every leprechaun. Be creative in
the presentation of your results, striving for aesthetics and
clarity.
Posted: Thu - February 1, 2007 at 04:27 PM