Solution for
Programming Exercise 8.1
THIS PAGE DISCUSSES ONE POSSIBLE SOLUTION to
the following exercise from this on-line
Java textbook.
Exercise 8.1:
An example in Section 8.2 tried to answer the
question, How many random people do you have to select before you find
a duplicate birthday? The source code for that program can
be found in the file BirthdayProblemDemo.java.
Here are some related questions:
- How many random people do you have to select before you find three
people who share the same birthday? (That is, all three people were born
on the same day in the same month, but not necessarily in the same year.)
- Suppose you choose 365 people at random. How many different birthdays
will they have? (The number could theoretically be anywhere from
1 to 365).
- How many different people do you have to check before you've found
at least one person with a birthday on each of the 365 days of the year?
Write three programs to answer these questions. Like the
example program, BirthdayProblemDemo, each of your programs
should simulate choosing people at random and checking their birthdays.
(In each case, ignore the possibility of leap years.)
Discussion
The original program has a subroutine, birthdayProblem(),
that does the simulation once. The main() routine calls
this subroutine over and over, as long as the user wants to continue.
The three programs can all use the same main() routine,
along with a modified birthdayProblem() routine. The changes
from the original program are not huge, but you need a clear understanding
of arrays in order to get them right. Let's look at each of the problems
in turn. I'll just look at the birthdayProblem() subroutines.
The complete programs are given below.
The first question asks how many people you have to choose at random
before finding three who share the same birthday. This is similar to
the original program, but instead of just checking whether or not a
given birthday has already been found, we need to keep track of how
many people have been found with each birthday. Where the original
program used an array of booleans, here we need an array
of ints. We still want to count the number of people we
check and output that count at the end.
An algorithm for the simulation is:
Let count = 0
Repeat:
Select a birthday at random
Add one to count
If this is the third time that birthday has occurred:
break out of the loop
Add one to the number of times that birthday has been found
Output the count
To do the counting, we need an array "int[] numFound",
where numFound[i] will be the number of times the i-th
day of the year has occurred as a birthday. Since numFound[i]
can be used in any way that any int variable can be used,
we can add one to the number stored in numFound[i] by
saying "numFound[i]++". When we create the array
with the command "numFound = new int[365]", all the elements
of the array are automatically initialized to zero. This is the initial
value that we want. (This is an important thing to remember! In some
programming languages, arrays are not automatically filled with zeros,
so it would be necessary to use a for loop to store a zero
into each place in the array. Even in Java, if you wrote this
program differently and reused the same array rather than creating a
new one for each simulation, you would have to remember to set
each element of the array to zero at the beginning of the simulation.)
Given all this, we can translate the algorithm into Java as follows:
int[] numFound; // numFound[i] will be the number of people
// who have been found who have a birthday
// on the i-th day of the year
int count; // The number of people who have been checked.
numFound = new int[365]; // Initially, all entries are 0.
count = 0;
while (true) {
// Select a birthday at random, from 0 to 364.
// If the same birthday was already seen twice
// before, then quit. Otherwise, add one to
// the corresponding entry in the numFound array
// to record that a person with that birthday
// has been found.
int birthday; // The selected birthday.
birthday = (int)(Math.random()*365);
count++;
if ( numFound[birthday] == 2 )
break; // It's the third time we've found this birthday.
numFound[birthday]++;
}
TextIO.putln("It took " + count +
" tries to find three people with the same birthday.");
The lines shown in red are the ones that differ significantly
from the original program.
This becomes the body of the birthdayProblem() subroutine
in the first program.
.
For the second program, we know exactly how many people we want to
check: 365. This calls for using a for loop. The information we
need for each birthday is whether or not that birthday has occurred.
For that, we can use an array of booleans. The value stored
in position i of the array is true if the i-th
day of the year has occurred as a birthday and is false if not.
After checking 365 people, we have to go through the array and count
the number of entries in the array that are true. This is
the number of different birthdays that have been found. The algorithm
can be expressed as:
Let used = new boolean[365]
Repeat 365 times:
Select a birthday at random
Store true into the corresponding location in the array, used
Let count = 0
for day = 0 to 364:
If used[day] is true:
Add 1 to count
Output the value of count.
This translates easily into Java code:
boolean used[]; // used[i] will be true if a person is found
// whose birthday is the i-th day of the year.
used = new boolean[365]; // Initially, all entries are false!
for (int i = 0; i < 365; i++) {
// Select a random birthday and record it.
int birthday; // The selected birthday.
birthday = (int)(Math.random()*365);
used[birthday] = true;
}
int count = 0;
for (int day = 0; day < 365; day++) {
// If this day occurred as a birthday, count it.
if (used[day] == true)
count++;
}
TextIO.putln("Among 365 people, there were " + count
+ " different birthdays.");
It might be worth noting that the test "if (used[day] == true)"
can be written more simply as "if (used[day])". Also,
the three lines in the first for loop could be reduced to
the single command "used[(int)(Math.random()*365)] = true;".
Of course, this one-line version is harder to understand.
The third program is just a little bit trickier. We have to continue
selecting people at random until we have found 365 different birthdays.
We can use a counter to keep track of how many different birthdays we
have found. We have to continue until this counter reaches 365.
We need a second counter to keep track of how many
different people we have checked. It's the second counter whose
value we want to output at the end. Now, we have to be able to
recognize whether a birthday we've just found is new, or whether we've
encountered it previously. For this, we can again use an array of booleans.
An algorithm for the simulation is:
Let used = new boolean[365]
Let count = 0 // The number of people checked
Let birthdaysFound = 0 // The number of different birthdays found
while birthdaysFound < 365:
Add one to count
Select a birthday at random
if used[birthday] is false:
Add one to birthdaysFound // since this is a new birthday
Let used[birthday] = true // so we don't count it again
Output the value of count
In Java, this algorithm becomes:
boolean[] used; // For recording the possible birthdays
// that have been seen so far.
int count; // The number of people who have been checked.
int birthdaysFound; // The number of different birthdays that
// have been found.
used = new boolean[365]; // Initially, all entries are false.
count = 0;
birthdaysFound = 0;
while (birthdaysFound < 365) {
// Select a birthday at random, from 0 to 364.
// If the birthday has not already been used,
// add 1 to birthdaysFound.
int birthday; // The selected birthday.
birthday = (int)(Math.random()*365);
count++;
if ( used[birthday] == false )
birthdaysFound++;
used[birthday] = true;
}
TextIO.putln( count + " people were checked." );
The Solution
Finding three people with the same birthday:
/*
How many random people do you have to select before you find
THREE with the same birthday (that is, three people who were born
on the same day of the same month, but not necessarily in the
same year). This program simulates the process. (It ignores the
possibility of people born on leap day.)
*/
public class BirthdayProblem2 {
public static void main(String[] args) {
TextIO.putln("This program simulates taking people at random");
TextIO.putln("until three have been found who were born on the");
TextIO.putln("same day of the year.\n");
do {
birthdayProblem();
TextIO.put("\nAgain? ");
} while ( TextIO.getlnBoolean() );
TextIO.putln("\n\nOK. Goodbye.");
} // end main()
static void birthdayProblem() {
// Simulate choosing people at random and checking the
// day of the year they were born on. If the person is
// the third who was born on that day of the year, stop,
// and output the number of people who were checked.
int[] numFound; // numFound[i] will be the number of people
// who have been found who have a birthday
// on the i-th day of the year
int count; // The number of people who have been checked.
numFound = new int[365]; // Initially, all entries are 0.
count = 0;
while (true) {
// Select a birthday at random, from 0 to 364.
// If the same birthday was already seen twice
// before, then quit. Otherwise, add one to
// the corresponding entry in the numFound array
// to record that a person with that birthday
// has been found.
int birthday; // The selected birthday.
birthday = (int)(Math.random()*365);
count++;
if ( numFound[birthday] == 2 )
break;
numFound[birthday]++;
}
TextIO.putln("It took " + count +
" tries to find three people with the same birthday.");
} // end birthdayProblem()
} // end class BirthdayProblem2
How many different birthdays do 365 people have?
/*
This program simulates selecting 365 people at random and finding
how many different birthdays they have among them.
*/
public class BirthdayProblem3 {
public static void main(String[] args) {
TextIO.putln("This program simulates taking 365 people at random");
TextIO.putln("and finding out how many different birthdays they");
TextIO.putln("have among them.\n");
do {
birthdayProblem();
TextIO.put("\nAgain? ");
} while ( TextIO.getlnBoolean() );
TextIO.putln("\n\nOK. Goodbye.");
} // end main()
static void birthdayProblem() {
// Simulate choosing people at random and checking the
// day of the year they were born on. The number of
// different days found among 365 people is counted
// and output.
boolean used[]; // used[i] will be true if a person is found
// whose birthday is on the i-th day of the year.
used = new boolean[365]; // Initially, all entries are false.
/* Choose 365 days at random, and mark each day by
setting the corresponding entry in the array, used,
to true. (If the value is already true, it doesn't
matter. We are only interested in whether or not
the birthday occurs, not how many times it occurs.)
*/
for (int i = 0; i < 365; i++) {
int birthday; // The selected birthday.
birthday = (int)(Math.random()*365);
used[birthday] = true;
}
/* Now, count how many entries in the used array are true.
This is how many different birthdays were found.
*/
int count = 0;
for (int day = 0; day < 365; day++) {
// If this day occurred as a birthday, count it.
if (used[day] == true)
count++;
}
TextIO.putln("Among 365 people, there were " + count
+ " different birthdays.");
} // end birthdayProblem()
} // end class BirthdayProblem3
Finding 365 different birthdays:
/*
How many random people do you have to select before you
have found someone with every possible birthday (ignoring
leap years)? This program simulates the process.
*/
public class BirthdayProblem4 {
public static void main(String[] args) {
TextIO.putln("This program simulates taking people at random");
TextIO.putln("until someone has been found with a birthday");
TextIO.putln("on every day of the year.\n");
do {
birthdayProblem();
TextIO.put("\nAgain? ");
} while ( TextIO.getlnBoolean() );
TextIO.putln("\n\nOK. Goodbye.");
} // end main()
static void birthdayProblem() {
// Simulate choosing people at random and checking the
// day of the year they were born on. People are chosen
// until all 365 possible birthdays (ignoring leap years)
// have been found. Then the number of people surveyed
// is output.
boolean[] used; // For recording the possible birthdays
// that have been seen so far. A value
// of true in used[i] means that a person
// whose birthday is the i-th day of the
// year has been found.
int count; // The number of people who have been checked.
int birthdaysFound; // The number of different birthdays that
// have been found.
used = new boolean[365]; // Initially, all entries are false.
count = 0;
birthdaysFound = 0;
while (birthdaysFound < 365) {
// Select a birthday at random, from 0 to 364.
// If the birthday has not already been used,
// add 1 to birthdaysFound.
int birthday; // The selected birthday.
birthday = (int)(Math.random()*365);
count++;
if ( used[birthday] == false )
birthdaysFound++;
used[birthday] = true;
}
TextIO.putln( count + " people were checked." );
} // end birthdayProblem()
} // end class BirthdayProblem4
[ Exercises
| Chapter Index
| Main Index
]
