Solution for Programming Exercise 3.7
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 3.7:
An example in Subsection 3.8.3 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 BirthdayProblem.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. Each of your programs should simulate choosing people at random and checking their birthdays. (In each case, ignore the possibility of leap years.)
The original program and the three programs for this exercise have some similarities, and we will use ideas from the original program. However, each part of this exercise presents its own problem.
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
The original program used a boolean array to keep track of whether or not each day had been seen. For this proble, we need to know how many times each day has been seen. That means that instead of one boolean value for each day, we need one integer value for each day. So, 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]++" or "numFound[i] = numFound[i] + 1". 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 reuse the same array rather than creating a new one for each use, you would have to remember to set initialize each element of the array before reusing it.)
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]++; } System.out.println("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 main() 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. After the for loop, value stored in position i of the array will 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 boolean 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 (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 (day = 0; day < 365; day++) {
// If this day occurred as a birthday, count it.
if (used[day] == true)
count++;
}
System.out.println("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 -- and elegantly -- 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;
}
System.out.println( count + " people were checked." );
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 {
/**
* 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.
*/
public static void main(String[] args) {
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]++;
}
System.out.println("It took " + count +
" tries to find three people with the same birthday.");
}
} // 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 {
/**
* 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.
*/
public static void main(String[] args) {
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.)
*/
int i;
for (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;
int day;
for (day = 0; day < 365; day++) {
// If this day occurred as a birthday, count it.
if (used[day] == true)
count++;
}
System.out.println("Among 365 people, there were " + count
+ " different birthdays.");
}
} // 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 {
/**
* 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.
*/
public static void main(String[] args) {
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;
}
System.out.println( count + " people were checked." );
}
} // end class BirthdayProblem4