One of the things that computers are particularly good at is doing “the same thing over and
over” in extremely tedious calculations. One of the applications for this is producing all the
possible combinations of groups of things – for example, imagine you have 3 pennies in your
pocket, and you flip them, one at a time, producing Heads(H), Tails(T), and Heads(H). Think of
the sequence H,T,H as being one possible combination (outcome) of your coin flipping
experiment.
If we wanted to write a computer program to simulate ALL possible combinations of the
flipping of your 3 pennies, the following algorithm would be just the ticket:
int heads = 0; // let’s let the value 0 represent a heads coin toss
int tails = 1; // let’s let the value 1 represent a tails coin toss
for (int coin1 = heads; coin1 <= tails; coin1++) {
for (int coin2 = heads; coin2 <= tails; coin2++) {
for (int coin3 = heads; coin3 <= tails; coin3++) {
String coin1str = "";
if (coin1 == 0)
coin1str = "H";
else
coin1str = "T";
String coin2str = "";
if (coin2 == 0)
coin2str = "H";
else
coin2str = "T";
String coin3str = "";
if (coin3 == 0)
coin3str = "H";
else
coin3str = "T";
System.out.println(coin1str + ”,” + coin2str + “,” + coin3str);
} // end of possibilities for coin3
} // end of possibilities for coin2
} // end of possibilities for coin1
Put this code into a Java program, compile it, run it, notice exactly what happens, and study the
code carefully so that you understand how it is doing what it is doing.
(See next page for problem statement)
Problem Statement: Jeff Bezos has decided to have a party at his mansion, and he’s invited 50
couples. As the couples arrive at the mansion, they receive a ticket with a number (like at the
deli counter), with the first couple receiving the tickets labeled 1 and 2, the second couple
getting 3 and 4, and so on. Jeff has noticed in the past that when he throws parties,
conversation groups most often occur in groups of 4 people. Being a nerd, he wonders:
Exactly how many different conversation groups of 4 are possible at this party?
He writes himself a short Java program, and in minutes he has his answer....
(An important small hint – the person who has the ticket with a “1” on it can only (obviously)
occur once in a given group – so, for example the grouping 1, 1, 2, 3 could NEVER occur!)
1) Step one – the “top” would be defined as:
Generate all possible UNIQUE combinations of the integers 1 – 100 inclusive,
and count them.
2) Step two – understand the problem. This problem differs a bit from the coin-flipping
problem – it’s certainly possible to have two coins come up as “heads”, but it’s NOT possible for
one guest to show up in the same conversation twice! Also, in the first problem, the sequence
of coin flips mattered - H, T, H is different from H, H, T – but in this problem if guests whose
number are 10, 20, 30, and 40 occur in ANY order, that represents the same conversation, so
we need to be careful not to “overcount”. (10,20,30,40 is the same conversation group at
40,30,20,10)
Let’s imagine we have a fixed group of people for the first three members of group of 4. (for
example, people numbered 1, 2, and 3 are already in the group). We need to now add a fourth
member, but that fourth member cannot take the value of any of the other three – we can do
this with a loop.
So: Starting with “the int of person 3 plus 1”, loop over all the possible int identities
for person four up to (and including 100).
This will give us: 1,2,3,4 1,2,3,5 1,2,3,6 .... 1,2,3,100
Now, once we’ve exhausted all the possibilities for person four, we need to do this FOR EACH
AND EVERY POSSIBLE identity for person three, then we do BOTH these loops for every
possibility for person two, and then for person one.
Step 3: Psuedocode - What we’ll end up with is 4 loops, nested inside one another:
initialize a counter to 0;
for each possible int value for personOne (starting at 1, ending at 100-3)
for each possible int value for personTwo (starting at personOne+1, ending at 100-2)
for each possible int value for personThree(starting at personTwo+1, ending at 100-1)
for each possible int value for personFour(staring at personThree+1, ending at 100)
increment the count
output the result;
The reason we start the counts at the value of the previous person “plus one” is that we don’t
ever want these integers to be the same (one person cannot occur twice in the conversation
group) – this technique ensures that this will never happen. It will also ensure that we don’t
over count because personOne < personTwo < personThree < personFour. (Make sure you
think about and understand why this is so)
Step 4: Translate pseudocode into code - take the pseudocode and produce a working
program! Upload this program (your HW3.java source code file) in a subdirectory of your
respository called “HW3” to gitlab.cs.uno.edu.
Bonus 1 (10 points, required for Honors Students) – Make a copy of your program in a
subdirectory of HW3, called bonus1. Modify the code so that it calculates the number of 5
person conversation gropus.
Bonus 2 (10 points) - How many of these 4 person groups contain paired-up couples? (think
about the relationship of the numbers that must occur, assuming everyone is assigned a unique
number as above). Make a copy of your program in a subdirectory of HW3, called bonus2.
Modify the code so that it calculates and outputs the number of groups containing couples who
came to the party together.
For similar assignments contact support@hamnicwritingservices.com or place your order at HAMNIC Solutions
Comments
Post a Comment