Handed out: 11/10/09
Note. When you read this assignment, it will sound like a huge job. It is not really that large. Just tackle it a bit at a time, and keep things simple. Avoid making things overly complicated. If you do not see how to do something, ask questions. If you are lost, try showing on paper what you are trying to accomplish. If you are unable to do that, ask for help.
Sometimes it is useful for a computer to produce a random number. Most computers do not have the ability to produce a genuinely random number, but there are methods for creating numbers that are apparently random, or pseudo-random. For lab assignment 3 (part 2) and lab assignment 9 you made use of a pseudo-random number generator from the Java library, provided by a class called Random.
The idea of a pseudo-random number generator is to define a function next(n) that takes an integer argument and produces an integer result. You start with an integer called the seed. Define r0 to be the seed. Then define
r1 = next(r0)etc. That gives you a sequence of integers r1, r2, r3, ...
r2 = next(r1)
r3 = next(r2)
For example, suppose that you define next(n) = (17*n + 1) mod 23. Suppose the seed is chosen to be 2. Then the sequence of numbers is
r0 = 2Notice that next(2) = 12 because (17*2 + 1) mod 23 = 35 mod 23 = 12.
r1 = next (2) = 12
r2 = next (12) = 21
r3 = next (21) = 13
...
Since the integers in our sequence will all be less than 23, the sequence repeats after a while. It goes 12, 21, 13, 15, 3, 6, 11, 4, 0, 1, 18, 8, 22, 7, 5, 17, 14, 9, 16, 20, 19, 2, 12, 21, 13, 15, ... You do not want to use so many pseudo-random numbers that the sequence starts to repeat, since then it hardly looks random.
You can also get a pseudo-random real number between 0 and 1 by taking the integers and dividing by an integer that is just larger than the largest possible integer in the sequence. For example, for our simple function next(n) = (17*n + 1) mod 23, define real number xi = ri / 23. Then the sequence of real numbers, starting with seed 2, is
x1 = r1/23 = 12/23 = 0.5217
x2 = r2/23 = 21/23 = 0.9130
x3 = r3/23 = 13/23 = 0.5652
...
Different pseudo-random number generators use different functions next(n). One kind, called a linear congruential pseudo-random number generator, uses next(n) = (a*n + b) mod c, where a and c are prime numbers, a < c and b < c. Generally, you choose c to be fairly large, so that it takes a long time before the sequence starts to repeat. But you must keep it small enough that performing the required arithmetic does not overflow the capacity of the integers that you are using. You can use the fact that 19872889 and 10237763 are prime. They are about the right size, if you use type long for your arithmetic, not type int. Notice that 10237763 < 19872889. So you can define
next(n) = (10237763*n + b) mod 19872889.
This section explains how you can use a pseudo-random number generator object, assuming that an appropriate class has already been created.
Suppose that there is a class called MyRandom that has two public things (and some number of private things). It has a constructor MyRandom(n), where n is an integer, that creates a new object with seed n. It also has a public method nextReal( ) that produces the next real number between 0 and 1. Each time you use the nextReal method, you get another pseudo-random number, as long as you do not get so many that the sequence repeats.
For example, the following function creates a pseudo-random number generator object called R and uses it to add up n pseudo-random numbers. It is only given as an example of using a pseudo-random number generator; this function will not be part of your assignment.
public static double randomSum(int n, int seed)
{
int k;
double sum;
MyRandom R = new MyRandom(seed);
k = 0;
sum = 0.0;
while(k < n) {
sum = sum + R.nextReal();
k++;
}
return sum;
}
Here is another example function. It rolls a die, obtainig a result that is an integer from 1 to 6. It does not want to create a new random number generator for each roll of the die, so it has a random number generator as a parameter, and uses that object to get a random number.
public static int rollDie(MyRandom R)
{
return (int)(6.0*R.nextReal()) + 1;
}
Write a definition of a pseudo-random number generator class. It should have the following components.
A private variable of type long that remembers the current integer in the sequence.
Private static constants a, b and c, which are the constants used in the next method. Define them as follows. (The word final means that you are not allowed to change them while the program runs. Of course, you can still edit the program to change them.)
private static final long a = 10237763; private static final long b = 17; private static final long c = 19872889;
A private static method next(n) that returns the integer that follows n in the sequence. Here is a suggestion of the next method in that class.
private static long next(long n)
{
return (a*n + b) % c;
}
A public constructor that takes an integer seed and stores it into the variable (see item 1).
A public method nextReal( ) that returns the next real number in the sequence, and also updates the variable (item 1) to hold the next integer in the sequence.
A public method rollDie( ) that returns a pseudo-random integer from 1 to 6. (It should use nextReal( ). The example of rollDie above takes the random number generator as a parameter. But you do not need to do that here. Method rollDie now lives inside an object, and it should use that same object's nextReal( ) method. Do not declare rollDie to be static.
Write a clear, precise and concise contract for each method.
TEST YOUR CLASS. Write a main function that creates a pseudo-random number generator object and uses it to generate several random numbers. Try using rollDie several times. Do the results look reasonable? Do not proceed until this class appears to be working correctly. Note: You can never test a pseudo-random number generator by getting just one number. Get several.
Note. Java is very picky about where you define main. Put your MyRandom class in a file called Assn10.java. In that file, put two classes, the MyRandom class and another just called Assn10. Only make the Assn10 class public, and put main inside class Assn10. So your program will be as follows, with ... indicating details that are left out.
public class Assn10
{
public static void main(String[] args)
{
...
}
}
class MyRandom
{
...
}
The rules of Craps are described below. The second part of your assignment is to add another class to your program that simulates games of Craps. Make your main function read an integer n from the user and play n games of Craps. The main function will create an object of class Craps and then ask that object to play n games by calling a method play n times. Method play will play one game. At the end of the games, the main function should report how many of the games were passed, how many did not pass, and the fraction of the games that passed.
|
The rules of Craps are as follows. The game is played with two dice. The player throws the dice to begin. If the outcome (the sum of the dice) is 7 or 11, the player passes (wins), and the game is over. If the outcome is 2, 3 or 12, the player does not pass, and the game is over. If the outcome of the first throw is anything except 2,3,7,11 or 12, then the outcome of the first throw becomes the players point. The player repeatedly tosses the dice until either he or she throws a value equal to the point (in which case the player passes) or the player throws a 7 (in which case the player does not pass). |
When the play method is asked to play a game, it should print what is happening. When it is done, play should return a result indicating whether the game ended in a pass or a not. Here is a sample output from the entire program (consisting of several games). For each game, the sequence of dice sums thrown should be shown. They are shown in parentheses in front of the final result. (Note: You will not get exactly these results. This is just to show the general appearance.) The first two lines are from main. Each line after that begins with Game i., written by main. The rest of each of those line is written by play. The last line is written by main.
What is the seed? 39228
How many games shall I play? 4
Game 1. (7) Pass
Game 2. (3) No pass
Game 3. (4 8 5 7) No pass
Game 4. (8 10 8) Pass
There were 2 passes and 2 nonpasses, for a fraction of 0.500 passes.
Start a class called Craps. It has the form
class Craps
{
}
where you have not filled in the body yet.
Create a private variable of type MyRandom. It will be a pseudo-random number generator to use during the computation.
Create a constructor that takes a pseudo-random number generator of class MyRandom and stores it into the private variable that was created in the preceding step.
Define the play method. It can use the pseudo-random number generator that you have stored. If that variable is called rand, then play should simulate the first roll of the dice using rand.rollDie() + rand.rollDie(). Be sure to print the first roll. Check to see whether the game is over after the first roll. If not, remember the point. Do a loop, rolling the dice until either the point or 7 is rolled. Remember to show each roll.
Include a clear and concise contract for play.
Modify the main method to read the information, create a new MyRandom object using the acquired seed, create a new Craps object using that MyRandom object, and then play the requested number of games. Keep track of the number of passes so that you can write the fraction of passes at the end.
Test your program, and look at the results. Do they look reasonable? (In the long run, a player will pass about 49.3% of the time.) If you change the seed, do the results change? They should.
Warning. When you throw two dice, be sure to throw two separate dice. Do not just throw one die and double it. You will not get the same results. For example, if you throw one die and double it, you will always get an even number, and can never get 7.
Turn in a printout of your program, showing all three classes (Assn10, MyRandom and Craps). Be sure your name is on the assignment.