with a newline (\n
) separating each line, the output will display properly.
4. Selection
Life is a sum of all your choices.
4.1. Problem: Monty Hall simulation
There’s a famous mathematical puzzle called the Monty Hall problem, based on the television show Let’s Make a Deal hosted by the eponymous Monty Hall. In this problem, you’re presented with three doors. Two of the three doors have junk behind them.  If you can choose that door, you win the gold. After you make an initial choice, Monty, who knows which door the pile of gold is behind, will open one of the two other doors, always picking a door with junk behind it. If you chose the gold door, Monty will pick between the two junk doors randomly. After opening a door, Monty gives you a chance to switch to the other unopened door. You decide to switch or not, the appropriate door is opened, and you win either junk or a pile of gold, depending on your luck.
As it turns out, it’s always a better strategy to switch doors. If you keep your initial choice, you have a 1 in 3 chance to win the gold. However, if you switch doors, you’ll have a 2 in 3 chance. The problem is counterintuitive and leads many people, including mathematicians and people holding advanced degrees, to the incorrect answer.
Think about it this way: Suppose you could pick two doors to open, and if the gold was behind either one of them, you’d win. Clearly, you’d have a 2 in 3 chance of winning. Monty allows you this option. Just pick the two doors you want and tell Monty the third. He reveals one of your two initial doors as junk, and you switch to the other one.
If you still aren’t convinced, that’s fine. Your goal is to write a program that simulates the Monty Hall dilemma, allowing a user to guess a door and then potentially switch. Once you’ve written the simulation, you can choose to play repeatedly and see how well you do if you switch.
A Monty Hall scenario has two significant features that distinguish it
from problems in previous chapters. First, randomness play a role.
Generating random numbers has become an important part of computer
science, and most languages provide programmers with tools for
generating random or practically random numbers. Recall the Random
class
from Chapter 3. With an object of
type Random
called random
, you can generate a random int
between
0
and n - 1
by calling random.nextInt(n)
.
The second and much more important feature of Java in the solution to this problem is the element of choice. A random door is chosen to hide gold, and the program must react appropriately. The user chooses a door, and the program must carefully choose another door to open in response. Finally, the user must decide whether or not he or she wants to switch his or her choice. Inherent in this problem is the idea of conditional execution. Every program from the previous chapter runs sequentially, line by line. With conditional execution, only some of the code may be executed, depending on input from the user or the values that random numbers take. Previously, every program was deterministic, a series of inevitable consequences. Now, that linear, one-thing-follows-another paradigm has split into complex trees and webs of possible program executions.
4.2. Concepts: Choosing between options
Before we get to random numbers and the complex choices involved in the Monty Hall problem, let’s talk about the simplified approach that most programming languages take to conditional execution. When we come to a point in a program where there is a choice to be made, we can think of it as the question, “Do I want to perform this series of tasks?” Like the classic game of 20 Questions, these questions in Java generally only have two answers: “yes” or “no.” If the answer is “yes,” the program completes Task A, otherwise it completes Task B. It’s easier to design programming languages that can handle yes-or-no questions than any general question. If you’ve studied logic in the past, you have probably run across Boolean logic. Boolean logic gives a set of rules, similar to the rules of traditional algebra, that can be applied to a system with only two values: true and false.
4.2.1. Simple choices
Because we want to build a system using only yes-or-no questions, Boolean logic is a perfect fit for computer science. To conform with other computer scientists, we try to think of conditions in terms of true and false, instead of yes and no. Thus, we can begin to formulate the kinds of choices we want to make:
If it’s raining outside,
I’ll take my umbrella.
This statement is a very simple program, even though it’s not one executed by a computer. The person following this program asks herself, “Is it raining today?” If the answer is “yes,” then she’ll take her umbrella. We can abstract this idea a bit further by saying that raining outside is a condition p and that taking my umbrella is an action a. In other words, if p is true, then do a. We haven’t specified what is to be done if p is not true, although we can assume that the actor in this drama will not take an umbrella.
If we want to view p as a decision to make, we can specify what happens if it’s not true. For example, we could formulate another choice:
If I have at least $50 in my pocket,
I’ll eat a lobster dinner;
otherwise,
I’ll eat fast food.
In this case, we let having at least $50 be condition q, eating a lobster dinner be action b, and eating fast food be action c. Now we’ve created a decision. If q is true, the person will do action b, but if it’s false, she’ll do action c.
4.2.2. Boolean operations
Even by itself, the ability to pick between two options is powerful, but we can augment this ability in a couple of ways. First, we don’t have to rely on simple conditions. Using Boolean logic, we can make arbitrarily complex conditions.
If I’m bored, or it’s late and I can’t sleep,
I’ll watch television.
Someone following this program will watch television if he’s bored or if it’s late and he also can’t sleep. We can break the condition into three sub-conditions: I’m bored is condition x, it’s late is condition y, and I can’t sleep is condition z. We have connected these three conditions together using the words “and” and “or.” These two simple words represent powerful concepts in Boolean logic, AND and OR. When two conditions are combined with AND, the result is true only if both conditions are true. When two conditions are combined with OR, the result is true if either of the conditions is true.
We can create a table called a truth table to show all the possible values certain conditions can take. We’re going to use the symbol ∧ to represent the concept of AND and the symbol ∨ to represent the concept of OR. We’ll also abbreviate true to T and false to F.
Given a condition x, a condition y, and the condition made by x ∧ y, this truth table shows all possible values. As stipulated, x ∧ y is true only when both x and y are true.
| x | y | x ∧ y |
|---|---|---|
T |
T |
T |
T |
F |
F |
F |
T |
F |
F |
F |
F |
This truth table gives all the values for x ∨ y. As you can see, x ∨ y is true if x or y are true.
| x | y | x ∨ y |
|---|---|---|
T |
T |
T |
T |
F |
T |
F |
T |
T |
F |
F |
F |
There’s confusion surrounding the word “or” in English. Sometimes “or” is used in an exclusive sense to mean one or the other but not both, as in, “Would you like lemonade or iced tea with your meal?” In logic, this exclusive or exists as well and is called XOR. This difference gives another reason for a formally structured language like mathematics or Java to express ourselves precisely. When two conditions are connected with XOR, the result is true if one or the other but not both conditions are true. We use the symbol ⊕ to represent the XOR operation in the truth table below.
This truth table gives all the values for x ⊕ y.
| x | y | x ⊕ y |
|---|---|---|
T |
T |
F |
T |
F |
T |
F |
T |
T |
F |
F |
F |
The operations AND, OR, and XOR are all binary operations like addition and multiplication. They connect two conditions together to get a result. There’s also a single unary operation in Boolean logic, the NOT operator. A NOT simply reverses a condition. If a condition is true, then NOT applied to that condition will yield false, and vice versa.
Here’s a truth table for NOT, using the symbol ¬ to represent the NOT operation.
| x | ¬x |
|---|---|
T |
F |
F |
T |
Now that we’ve nailed down some notation for Boolean logic, we can express the complicated expression that sent us down this path in the first place. Recall that x is I’m bored, y is it’s late, and z is I can’t sleep. Let d be the action I’ll watch television. We can express the choice in this way: If x ∨ (y ∧ z), then do d. Using this notation, we’ve expressed precisely the conditions for watching television, using parentheses to clear up the ambiguity present in the original statement. If we can map individual conditions to Boolean variables, we can build conditions of arbitrary complexity.
4.2.3. Nested choices
Making one choice is all well and good, but in life and computer programs, we may have to make many interrelated choices. For example, if you choose to eat at a seafood restaurant, then you might choose between eating shrimp and lobster, but if you choose instead to eat at a steakhouse, the options of shrimp and lobster might not be available.
A nested choice is one that sits inside of another choice you’ve already made. We could describe choices of restaurants and meals as follows.
If I want seafood,
I’ll eat at Sharky’s, where
if I have at least $50,
I’ll order the lobster;
otherwise,
I’ll order the shrimp.
But if I don’t want seafood,
I’ll eat at the Golden Calf, where
if I have at least $30,
I’ll order the filet mignon;
otherwise,
I’ll order the pork chops.
The previous description is long, but it precisely expresses the decisions our imaginary diner might make. This description in English has drawbacks: It’s long and repetitive, and the grouping of specific meal choices with specific restaurants isn’t clear.
In the next section, we discuss Java syntax that allows us to express the same sorts of decision patterns. Unlike English, Java has been designed to make these sequences of decisions clear and easy to read.
4.3. Syntax: Selection in Java
With some theoretical background on the kinds of choices we’re
interested in making, we can now discuss the Java syntax used to
describe these choices. It was no accident that we kept repeating the
word “if,” because the main Java language feature for making choices
is called an if
statement.
4.3.1. if
statements
The designers of Java studied Boolean logic and created a type called
boolean
. Every condition used by an if
statement must evaluate to a
boolean
value, which can only be one of two things: true
or false
.
For example, we could have a boolean
variable called raining
. Stored
in this variable is the value true
if it’s raining and false
if it
isn’t. Using Java syntax, we could encode our first example in which our
actor takes her umbrella when it’s raining.
if(raining) {
umbrella.take();
}
The action taken if it is raining is done by calling a method on an
object. We’ll discuss objects and methods further in
Chapter 8 and Chapter 9. What we’re
focusing on now is that the line umbrella.take();
is executed only if
raining
has the value true
. Nothing is done if it’s false
.
Figure 4.1 shows this pattern of conditional execution
followed by all if
statements.
if
statement when its condition is true
and skips past it otherwise.Our descriptions of logical scenarios from the previous section used the
word “then” to mark the actions that would be done if a condition was
true. Some languages use then
as a keyword, but Java doesn’t.
Instead, note the left brace ({
) and the right brace (}
) that
enclose the executable line umbrella.take();
. These braces serve the
same role as the word “then,” clearly marking the action to be
performed if a condition is true. Braces are unambiguous because they
mark a start and an end. If there are many actions to be done, they can
all be put inside the braces, and there will be no question as to which
actions are associated with a given if
statement.
For example, we may also need to close the window and put on a raincoat if it’s raining. We might accomplish these tasks in Java as follows.
if(raining) {
umbrella.take();
window.close();
raincoat.putOn();
}
Within a matching pair of braces ({ }
), called a block of code,
execution proceeds normally, line by line. First, the JVM will cause the
umbrella to be taken, then the window to be closed, and finally the
raincoat to be put on.
If only a single line of code is contained within a block of code, the braces can be left out. For example, many experienced Java programmers would have written our first example as follows.
if(raining)
umbrella.take();
For beginning Java programmers, however, it’s a good idea to use braces even when you don’t need to. Without braces, code can appear to be doing one thing when it’s really doing another.
Since programmers must often choose between two alternatives, Java
provides an else
statement to specify code that should be run when the
condition of the if
statement is false.
Let fiftyDollars
be a boolean
variable that’s true
if we have at
least $50 and is false
otherwise. Now, we can choose between two
dining options based on how much money we have.
if(fiftyDollars) {
lobsterDinner.eat();
}
else {
fastFood.eat();
}
This Java code matches the logical statements we wrote before. If we
have enough money, we’ll eat a lobster dinner; otherwise, we’ll eat fast
food. As with an if
statement, we use braces to mark a block of code
for an else
statement, too. Since a single line of code will be
executed in each case, the braces are optional here. We could have
written code with the same functionality as follows.
if(fiftyDollars)
lobsterDinner.eat();
else
fastFood.eat();
Figure 4.2 shows the pattern of conditional execution
followed by all if
statements that have a matching else
statement.
if
statement when its condition is true
and jumps into the else
statement otherwise.|
Pitfall: Misleading indentation
Indentation is used to make code more readable, but Java ignores whitespace, meaning that the indentation has no effect on the execution of the code. To demonstrate, let’s assume that our imaginary diner knows he’ll get a stomachache after eating fast food. Thus, he’ll take some Pepto-Bismol after eating it. If you added this action to the code above, which does not contain braces, you might get the following.
Although it looks like both
|
4.3.2. The boolean
type and its operations
Recall that Java uses the type boolean
for values that can only be
true or false. Just like the numerical types double
and int
, the
boolean
type has specific operations that can be used to combine them
together. By design, these operations correspond exactly to the logical
operations we described before. Here’s a table giving the Java
operators equivalent to the logical Boolean operations.
| Name | Math Symbol |
Java Operator |
Description |
|---|---|---|---|
AND |
∧ |
|
Returns |
OR |
∨ |
|
Returns |
XOR |
⊕ |
|
Returns |
NOT |
¬ |
|
Returns the opposite of the value |
Using these operators, we can create boolean
values and combine them
together.
boolean x = true;
boolean y = false;
boolean z = !((x || y) ^ (x && y));
When this code is executed, the value of z
will be false
. Although
it’s perfectly legal to perform boolean
operations this way, it’s
much more common to combine them “on the fly” inside of the condition
of an if
statement. Recall the statement from the previous section:
If I’m bored, or it’s late and I can’t sleep,
I’ll watch television.
If we let bored
, late
, and canSleep
be boolean
variables whose
values indicate if we are bored, if it is late, and if we can sleep,
respectively, we can encode this statement in Java like so.
if(bored || (late && !canSleep))
television.watch();
Combining the ||
operator with other ||
operators is both
commutative and associative: order and grouping doesn’t matter.
Likewise, combining the &&
operator with other &&
operators is
also commutative and associative. However, once you start mixing ||
with &&
, it’s a good idea to use parentheses for grouping. If, in
the above example, bored
is true
, late
is false
, and canSleep
is true
, then the expression bored || (late && !canSleep)
will be
true
. However, with the same values, the expression
bored || late && !canSleep
will be false
.
Now that we’re discussing ordering, note that ||
and &&
are short circuit operators. Short circuit means that, if
the value of the expression can be determined without evaluating the
rest of it, the JVM won’t bother to compute any more of the
expression. With ||
this situation arises because true
OR anything
else is still true
. With &&
this situations arises because false
AND anything else is still false
.
if(true || ((late && !canSleep && isTired && isHungry) ||
(wantsToFindOutWhatHappensNextInHisFavoriteShow ||
likesTV)))
The condition of this if
statement will always evaluate to true
, and
its body will always be executed. Because Java knows this, it won’t
even bother to check any of the conditions after the first ||
operator.
This short circuit evaluation is done at run time and will work if the
value of a variable at the beginning of an OR clause is true
. It need
not be the literal true
.
if(false && ((late || !canSleep || isTired || isHungry) &&
(wantsToFindOutWhatHappensNextInHisFavoriteShow ||
likesTV)))
The condition of this if
statement will always evaluate to false
and
its body won’t be executed. As before, nothing after the first &&
will even be checked. If you’re combining literals and boolean
values with the ||
and &&
operators, it makes no difference that
short circuit evaluation occurs. However, if a method call is part of
the clauses, your code might miss valuable side-effects. For example,
let the boolean
variable working
be false
in the following.
if(working && doSomethingImportant())
In this case, the doSomethingImportant()
method must return a
boolean
value to be a valid statement. Still, if working
is false
,
the doSomethingImportant()
method won’t even be called. As soon as the
JVM realizes that it’s applying the &&
operation to a false
value (or an ||
to a true
), it’ll give up. In many cases, doing so is fine. In fact,
programmers sometimes exploit this feature to allow code in a
method like doSomethingImportant()
to run only if it’s safe to do so.
In this case, if we assume that we always want to run the
doSomethingImportant()
method (because it does something important)
every time the condition of the if
statement is evaluated, we need to
restructure the code. For example, we can reverse the order of the two
terms in the AND clause to achieve this effect. Alternatively, Java
provides non-short circuit versions of the ||
and &&
operators,
namely |
and &
, if you need to force full evaluation.
You might have been wondering where the majority of boolean
values come
from. Most computer programs don’t ask the user a long series of true
or false questions before spitting out an answer. Most boolean
values
in Java programs are the result of comparisons, often of numerical data
types.
It’s can be useful to compare two numbers to see if one is larger, smaller, or
equal to the other. For example, you might have a double
variable
called pressure
that gives the water pressure in a hydraulic system.
Perhaps you also have a constant called CRITICAL_PRESSURE
that gives
the maximum safe pressure for your system. You can compare these values
using the >
operator.
if(pressure > CRITICAL_PRESSURE)
emergencyShutdown();
This code allows you to call the appropriate emergency method when
pressure
is too high. Of course, the >
operator is not the only way
to compare two values in Java. We list all the relational operators in
Chapter 3, but
the table below shows them again in a
mathematical context.
| Name | Math Symbol |
Java Operator |
Description |
|---|---|---|---|
Equals |
= |
|
|
Not Equals |
≠ |
|
|
Less Than |
< |
|
|
Less Than or Equals |
≤ |
|
|
Greater Than |
> |
|
|
Greater Than or Equals |
≥ |
|
|
The concepts and mathematical symbols for these operators should be
familiar from mathematics. There are a few differences from the
mathematical versions of these ideas that are worth pointing out. First,
only easy-to-type symbols are used for Java operators. Thus, we need two
characters to represent most relational operators in the language. These operators
can be used to compare any numerical type with any other numerical type,
including char
. In the case of mismatched types, such as an int
and
a double
, the lower precision type is automatically cast to the higher
precision type. Care should be taken when using the ==
operator with
floating-point types because of rounding errors. For example, the
expression 1.0/3.0 == 0.3333333333
always evaluates to false
.
The ==
operator is not the same as the =
operator from previous
chapters. In Java, the double equal sign ==
is used to compare two
things while the single equal sign =
is used to assign one thing to
another.
Confusion can also arise because, in the mathematical world, relational
symbols are used to make a statement: x < y is an
announcement or a discovery that the value contained in x
is, in fact, smaller than the value contained in y. In the
Java world, the statement x < y
is a test whose answer is true
if
the value contained in x
is smaller than the value contained in y
and false
otherwise. Using these operators means performing a test at
a specific point in the code, asking a question about the values that
certain variables or literals (or the results of method calls) have at
that moment in time. In another sense, using these comparisons is a way
to take numerical data and convert it into the language of boolean
values. Note that the following statement does not compile in Java.
if(4)
x = y + z;
To be used in an if
statement, the value 4
must be first compared
with some other numerical type to yield a true
or false
.
|
Pitfall: Assignment instead of equality
A common pitfall is to forget one of the equal signs in the comparison operator.
Again, this code won’t compile. If it did, the variable Extreme care should be taken when
comparing two
This code correctly calls the
In this case, |
The next few examples illustrate the use of the if
statement. They
also use some methods from class Math
.
In the standard Gregorian calendar, leap years occur roughly once every four years. During leap years, the month of February has 29 days instead of 28. This extra day makes up for the fact that it takes a little more than 365.24 days for the earth to orbit the sun. Unfortunately, the orbit of the earth around the sun doesn’t match up in any exact way with the rotation of the earth, making exceptions to the rule of every four years.
In fact, the official definition for a leap year is a year that is evenly divisible by 4, except for those years that are evenly divisible by 100, with the exception to the exception of years that are evenly divisible by 400. For example, 1988 was a leap year because it was divisible by 4. The year 1900 was not a leap year because it was divisible by 100 but not by 400, and the year 2000 was a leap year because it was divisible by 400.
Recall that the mod operator (%
) allows us to find the remainder
after integer division. Thus, if n % 100
gives zero, n
has no
remainder after being divided by 100
and must be evenly divisible by
100.
import java.util.*;
public class LeapYear {
public static void main(String[] args) {
Scanner in = new Scanner( System.in );
System.out.print("Please enter a year: ");
int year = in.nextInt();
if( year % 400 == 0 )
System.out.println(year + " is a leap year.");
else if( year % 100 == 0 )
System.out.println(year + " is not a leap year.");
else if( year % 4 == 0 )
System.out.println(year + " is a leap year.");
else
System.out.println(year + " is not a leap year.");
}
}
As with all of the programs in this section, we begin by importing
java.util.*
, which is needed for the Scanner
class for input. The
program prompts the user for a year and reads it in. If the year is
evenly divisible by 400, the program outputs that it’s a leap year.
Otherwise, if the year is evenly divisible by 100, the program outputs
that it is not a leap year. Otherwise, if the year is evenly divisible
by 4, the program outputs that it’s a leap year. Finally, if all the
other conditions have failed, the program outputs that the year is not a
leap year.
The quadratic formula is a useful tool from mathematics. Using this formula, you can solve equations of the form ax2 + bx + c = 0. You might recall the statement of the quadratic formula given below.
The b2 - 4ac part of the formula is called the discriminant. If the discriminant is positive, there will be two real answers to the equation. If the discriminant is negative, there will be two complex answers to the equation. Finally, if the discriminant is zero, there will be a single real answer to the problem. If you want to write a program to solve quadratic equations for you, it should take these three possibilities into account.
import java.util.*;
public class Quadratic {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("This program solves quadratic" +
" equations of the form ax^2 + bx + c = 0.");
System.out.print("Please enter a value for a: "); (1)
double a = in.nextDouble();
System.out.print("Please enter a value for b: ");
double b = in.nextDouble();
System.out.print("Please enter a value for c: ");
double c = in.nextDouble();
double discriminant = b*b - 4*a*c; (2)
if(discriminant == 0.0) (3)
System.out.println("The answer is x = " + (-b/(2*a)));
else if(discriminant < 0.0) (4)
System.out.println("The answers are x = " + (-b / (2*a)) + " + "
+ Math.sqrt(-discriminant) / (2*a) + "i and x = "
+ (-b / (2*a)) + " - " + Math.sqrt(-discriminant) / (2*a) + "i");
else (5)
System.out.println("The answers are x = " + (-b + Math.sqrt(discriminant))/(2*a)
+ " and x = " + (-b - Math.sqrt(discriminant))/(2*a));
}
}
| 1 | This program prompts the user and reads in values for a ,
b , and c . |
| 2 | Then, it computes the discriminant. |
| 3 | In the first case, we test to see if the discriminant is zero and print the single answer. |
| 4 | Next, if the discriminant is negative, we compute the real and complex parts separately and output the two answers. |
| 5 | Finally, if the discriminant is positive, we find the two real answers and output them. |
Note that braces were not needed for the if
,
else
-if
, and else
blocks because each is composed of only a single
line of code. Although these System.out.println()
method calls may
take up more than one line visually, Java interprets them as single
lines because they each only have a single semicolon (;
).
The line if(discriminant == 0.0)
is dangerous since we’re using
double
values. Because of rounding errors, the discriminant might not
be exactly zero even if it should be, mathematically. Industrial
strength code would probably check to see if the absolute value of the
discriminant is less than a very small number (such as 0.00000001).
Values that small would then be treated as if they were zero.
In the time-honored game of 20 Questions, one person mentally chooses something, and the other participants must guess what the thing is by asking questions whose answer is either “yes” or “no.” In one popular version, the person who chooses the thing starts by declaring whether it is animal, vegetable, or mineral.
Using counting principles from math, 20 yes-or-no questions makes it possible to differentiate 220 = 1,048,576 items. If you’re also told whether the thing is animal, vegetable, or mineral, it should be possible to guess over 3 million items! At this point in our development as Java programmers, we’re not yet ready to deal with such a large range of possibilities. To keep the size of the code reasonable, let’s narrow the field to 10 different items: a lizard, an eagle, a dolphin, a human, some lead, a diamond, a tomato, a peach, a maple tree, and a potato.
Using these items, we can construct a tree of decisions, starting with the decision between animal, vegetable, and mineral. If the thing is an animal, we could then ask if it is a mammal. If it is a mammal, we could ask if it lives on land, deciding between human and dolphin. If it’s not a mammal, we could ask if it flies, deciding between an eagle and a lizard. We can construct similar questions for the things in the vegetable and mineral categories, matching Figure 4.3.
import java.util.*;
public class TwentyQuestions {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Is it an animal, vegetable, or mineral? (a, v, or m): ");
String response = in.next().toLowerCase();
if(response.equals("a")) {
System.out.print("Is it a mammal? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y")) {
System.out.print(
"Does it live on land? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y"))
System.out.println("It's a human.");
else // Assume "n"
System.out.println("It's a dolphin.");
}
else { // Assume "n"
System.out.print("Does it fly? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y"))
System.out.println("It's an eagle.");
else // Assume "n"
System.out.println("It's a lizard.");
}
}
else if(response.equals("v")) {
System.out.print("Is it a fruit? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y")) {
System.out.print(
"Does it grown on a vine? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y"))
System.out.println("It's a tomato.");
else // Assume "n"
System.out.println("It's a peach.");
}
else { // Assume "n"
System.out.print("Is it a tree? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y"))
System.out.println("It's a maple tree.");
else // Assume "n"
System.out.println("It's a potato.");
}
}
else { // Assume "m"
System.out.print(
"Is it the hardest mineral? (y or n): ");
response = in.next().toLowerCase();
if(response.equals("y"))
System.out.println("It's a diamond.");
else // Assume "n"
System.out.println("It's lead.");
}
}
}
The code in this example is straightforward, although even 10 items
makes for a lot of if
and else
blocks. Other than the if
-else
statements, only simple input and output are needed to make the program
function. For proper String
comparison, it’s necessary to use the
equals()
method to test if two String
values are the same.
Note that we’ve added comments specifying what we assume is the case
for each else
block. If we were being more careful, we should test for
the "y"
and "n"
cases and then give an error message when the user
inputs something unexpected, like "x"
or "149"
or even "no"
.
Again, note that no braces are needed for the final if
-else
blocks
in which the guess is made, since each of these guesses requires only a
single line of code.
You might be curious how to make a real 20 Questions game that could learn over time. To do so, many more programming tools are necessary: repetition, data structures (so that you can organize the questions), and file input and output (so that you can store new information permanently). These concepts are covered in later chapters.
4.3.3. switch
statements
The if
statement is the workhorse of Java conditional execution. With
enough care, you can craft code that can make any fixed sequence of
decisions with arbitrary complexity. Even so, the if
statement can be
a little clumsy because it only allows you to choose between two
alternatives. After all, a conditional can only be true
or false
.
Certainly, decisions can be nested, allowing for more than two
possibilities, but long lists of possibilities can be cumbersome and hard to read.
For example, imagine that we want to create a program that determines the appropriate gift for a wedding anniversary. Below is a table of traditional categories of gifts based on the anniversary year.
| Year | Gift | Year | Gift | |
|---|---|---|---|---|
1 |
Paper |
13 |
Lace |
|
2 |
Cotton |
14 |
Ivory |
|
3 |
Leather |
15 |
Crystal |
|
4 |
Fruit |
20 |
China |
|
5 |
Wood |
25 |
Silver |
|
6 |
Candy / Iron |
30 |
Pearl |
|
7 |
Wool / Copper |
35 |
Coral |
|
8 |
Bronze / Pottery |
40 |
Ruby |
|
9 |
Pottery / Willow |
45 |
Sapphire |
|
10 |
Tin / Aluminum |
50 |
Gold |
|
11 |
Steel |
55 |
Emerald |
|
12 |
Silk / Linen |
60 |
Diamond |
Let year
be a variable of type int
containing the year in question.
A structure of if
-else
statements that can determine the appropriate
gift based on the year is below.
 Note that we are using the
feature of if
statements that treats an entire if
statement as one
statement. If we used braces to group things properly, the code would
become unreadable and unmanageably large.
String gift;
if(year == 1) {
gift = "Paper";
}
else {
if(year == 2) {
gift = "Cotton";
}
else {
if(year == 3) {
gift = "Leather";
}
else {
if(year == 4) {
gift = "Fruit";
}
.
.
.
It appears that there’s some kind of else if
construct in Java, but
there isn’t. Still, careful use of the rules for braces allows us to
write code that nicely expresses a sequence of alternatives.
Another way of expressing a long sequence of alternatives is by using a
switch
statement. A switch
statement takes a single integer type
value (int
, long
, short
, byte
, char
) or a String
and jumps
to a case corresponding to the input. We can recode the anniversary gift
example using a switch
statement as follows.
String gift;
switch(year) {
case 1: gift = "Paper"; break;
case 2: gift = "Cotton"; break;
case 3: gift = "Leather"; break;
case 4: gift = "Fruit"; break;
case 5: gift = "Wood"; break;
case 6: gift = "Candy / Iron"; break;
case 7: gift = "Wool / Copper"; break;
case 8: gift = "Bronze / Pottery"; break;
case 9: gift = "Pottery / Willow"; break;
case 10: gift = "Tin / Aluminum"; break;
case 11: gift = "Steel"; break;
case 12: gift = "Silk / Linen"; break;
case 13: gift = "Lace"; break;
case 14: gift = "Ivory"; break;
case 15: gift = "Crystal"; break;
case 20: gift = "China"; break;
case 25: gift = "Silver"; break;
case 30: gift = "Pearl"; break;
case 35: gift = "Coral"; break;
case 40: gift = "Ruby"; break;
case 45: gift = "Sapphire"; break;
case 50: gift = "Gold"; break;
case 55: gift = "Emerald"; break;
case 60: gift = "Diamond"; break;
default: gift = "No traditional gift"; break;
}
Just like an if
statement, a switch
statement always has parentheses
enclosing some argument. Unlike an if
, the argument of a switch
must
be some kind of data that can be expressed as an integer or a String
,
not a boolean
. For each of the possible values you want the switch
to handle, you write a case
statement. A case
statement consists of
the keyword case
followed by a constant value, either a literal or a
named constant, then a colon. When executed, the JVM jumps to the
matching case
label and starts executing code there. If there is no
matching case
label, the JVM goes to the default
label. If there is
no default
label, the entire switch
statement is skipped.
One unusual feature of switch
statements is that execution falls
through case
statements. This means that you can use many different
case
statements for a single segment of executable code. The execution
of code in a switch
statement jumps out when it hits a break
statement. However, break
statements are not required, as shown in
this switch
statement that gives location information for all of the
telephone area codes in New York state.
String location = "";
switch(code) {
case 917: location = "Cellular: ";
case 212:
case 347:
case 646:
case 718: location += "New York City"; break;
case 315: location = "Syracuse"; break;
case 516: location = "Nassau County"; break;
case 518: location = "Albany"; break;
case 585: location = "Rochester"; break;
case 607: location = "South Central New York"; break;
case 631: location = "Suffolk County"; break;
case 716: location = "Buffalo"; break;
case 845: location = "Lower Hudson Valley"; break;
case 914: location = "Westchester County"; break;
default: location = "Unknown Area Code"; break;
}
As you can see, five different area codes are used by New York City. By
leaving out the break
statements, values of 212
, 347
, 646
, and
718
all have "New York City"
stored into location
. Area code 917
was originally designated for cellular phones and pagers although now it
includes some landlines. By cleverly putting the statement for 917
ahead of
the other New York City entries, a value of 917
first stores
"Cellular: "
into location
and then falls through and appends
"New York City"
. For each of these five area codes, execution in the
switch
statement ends only when the break
statement is reached.
The remaining nine area codes are separate. Each of them does a
single assignment and then breaks out of the switch
block. Finally,
the default
label is used if the area code doesn’t match one of the
given codes. Note that we’ve ordered the (non-NYC) area codes in
ascending order for the sake of readability. As shown in the
917
example, there’s no rule about the ordering of the labels. Even
the default
label can occur anywhere in the switch
block you want,
although it’s common to put it at the end. Also, the break
after the
default
label is unnecessary because execution exits the switch
block anyway. Nevertheless, it’s always wise to end on a break
, in
the event that you add more cases in later.
Carelessness is always something to watch out for in switch
statements. Leaving out a break
statement can cause disastrous and
difficult to discover bugs. The compiler does not warn you about missing
break
statements, either. It’s entirely your responsibility to use them
appropriately. Because of the dangers involved, it’s often safe to
use if
-else
statements. Any switch
statement can be rewritten as
some combination of if
-else
statements, but the reverse is not true.
The benefit of switch
statements is their ability to list many
alternatives clearly. Their drawbacks include the ease of making a
mistake, an inability to express ranges of data or most types (double
,
float
, or any reference type other than String
), and limited
expressive power. They should be used only when their benefit of clearly
displaying a list of data outweighs the drawbacks.
Next we give a number of examples to help you get more familiar with
switch
statements.
There are fewer uses for switch
statements than if
statements.
Nevertheless, there are problems where their
fall-through behavior can be useful. Imagine that you need to write a
program that gives the length of each month (with the assumption that February always
has 28 days). Given the month as a number, we can use switch
statements to write a program
that maps the number of the month to the number of days it contains.
import java.util.*;
public class DaysInMonth {
public static void main(String[] args) {
Scanner in = new Scanner( System.in );
System.out.print("Please a month number (1-12): ");
int month = in.nextInt();
int days = 0;
switch( month ) {
case 2: days = 28; break; (1)
case 4:
case 6:
case 9:
case 11: days = 30; break; (2)
case 1:
case 3:
case 5:
case 7:
case 8:
case 10:
case 12: days = 31; break; (3)
}
System.out.println("The month you entered has " + days + " days.");
}
}
| 1 | This program has a single label for February setting days to 28. |
| 2 | Then, there are labels for April, June, September, and November, months that each have 30 days. |
| 3 | Finally, the large block of January, March, May,
July, August, October, and December all set days to 31. |
It would be
easy to extend this code to prompt the user for a year so that you could
integrate the leap year code from above for the February case. Note also
that we didn’t use a default
label. You might want to set days
to
some special value (like -1
) for invalid months.
In this program it’s necessary to initialize days
to some value, in this case 0
.
Otherwise, the program won’t compile, since it’ll try to print out the
value inside days
, a value that won’t exist if month
is not in the range 1 through 12.
The term ordinal numbers refers to numbers that are used for ordering within a set of items: first, second, third, and so on. When writing these numbers with numerals in English, it is common to append two letters to the end of the numeral to give the reader a clue that these numerals should be read with their ordinal names: 1st, 2nd, 3rd, and so on.
Unlike most things in English, the rules for deciding which two letters
are relatively simple. If the number ends in a 1, the letters “st”
should generally be used. If the number ends in a 2, the letters “nd”
should generally be used. If the number ends in a 3, the letters “rd”
should generally be used. For most other numbers, the letters “th”
should be used. We can use a switch
statement to write a program to
give the correct ordinal endings for most numbers as follows.
import java.util.*;
public class Ordinals {
public static void main(String[] args) {
Scanner in = new Scanner( System.in );
System.out.print("Please enter a positive number: ");
int number = in.nextInt();
String ending;
switch( number % 10 ) {
case 1: ending = "st"; break;
case 2: ending = "nd"; break;
case 3: ending = "rd"; break;
default: ending = "th"; break;
}
System.out.println("Its ordinal version is "
+ number + ending + ".");
}
}
This program prompts and then reads in an int
from the user. We then
find the remainder of number
when it’s divided by 10, yielding its
last digit. Based on this digit, we can pick from the four possibilities
and output the correct ordinal number in most cases. Unfortunately, the
names for English numbers have an inconsistent naming convention between 11 and 19, inclusive,
and the ordinals for any number ending in 11, 12, or 13 will be given the wrong
suffix by our code. We leave a more complete solution as an exercise.
Many cultures practice astrology, a tradition that the time of a person’s birth impacts his or her personality or future. One important element of Chinese astrology is their zodiac, consisting of 12 animals. Each consecutive year in a 12-year cycle corresponds to an animal. Because this system repeats, the year one is born in modulo 12 identifies the animal. Below is a table giving these values. For example, if you were born in 1979, 1979 mod 12 ≡ 11; thus, you would be a Ram. Note that this arrangement is based on years in the Gregorian calendar. Chinese astrologers do not list the Monkey as the first animal in the cycle. Note that the names of these animals are also sometimes translated in slightly different ways.
| Animal | Year modulo 12 |
Animal | Year modulo 12 |
|
|---|---|---|---|---|
Monkey |
0 |
Tiger |
6 |
|
Rooster |
1 |
Rabbit |
7 |
|
Dog |
2 |
Dragon |
8 |
|
Boar |
3 |
Snake |
9 |
|
Rat |
4 |
Horse |
10 |
|
Ox |
5 |
Ram |
11 |
Unfortunately, this table is not very accurate because it’s based on
numbering from the Gregorian calendar. The years in question actually
start and end based on Chinese New Year, which occurs between January 21
and February 20. As a consequence, you may miscalculate your animal if
your birthday is early in the year. Since calculating the date of
Chinese New Year is challenging, let’s ignore this problem for the
moment and write a program using a switch
statement designed to
correctly output the animal corresponding to an input birth year.
import java.util.*;
public class ChineseZodiac {
public static void main(String[] args) {
Scanner in = new Scanner( System.in );
System.out.print("Please enter a year: ");
int year = in.nextInt();
String animal = "";
switch( year % 12 ) {
case 0: animal = "Monkey"; break;
case 1: animal = "Rooster"; break;
case 2: animal = "Dog"; break;
case 3: animal = "Boar"; break;
case 4: animal = "Rat"; break;
case 5: animal = "Ox"; break;
case 6: animal = "Tiger"; break;
case 7: animal = "Rabbit"; break;
case 8: animal = "Dragon"; break;
case 9: animal = "Snake"; break;
case 10: animal = "Horse"; break;
case 11: animal = "Ram"; break;
}
System.out.println("The Chinese zodiac animal for this year is: " + animal);
}
}
| Sign | Symbol | Date Range |
|---|---|---|
Aries |
The Ram |
March 21 to April 19 |
Taurus |
The Bull |
April 20 to May 20 |
Gemini |
The Twins |
May 21 to June 20 |
Cancer |
The Crab |
June 21 to July 22 |
Leo |
The Lion |
July 23 to August 22 |
Virgo |
The Virgin |
August 23 to September 22 |
Libra |
The Scales |
September 23 to October 22 |
Scorpio |
The Scorpion |
October 23 to November 21 |
Sagittarius |
The Archer |
November 22 to December 21 |
Capricorn |
The Sea-Goat |
December 22 to January 19 |
Aquarius |
The Water Bearer |
January 20 to February 19 |
Pisces |
The Fishes |
February 20 to March 20 |
In Western astrology, an important element associated with a person’s birth is also called a zodiac sign. The dates for determining this kind of zodiac sign are given by the preceding table.
If you want to implement the rules for this zodiac in code, a switch
statement is a good place to start, but you also have to put if
statements for each month to test the exact range of dates.
import java.util.*;
public class WesternZodiac {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a month number (1-12): ");
int month = in.nextInt();
System.out.print("Please enter a day number in that month (1-31): ");
int day = in.nextInt();
String sign = "";
switch(month) {
case 1: if(day < 20)
sign = "Capricorn";
else
sign = "Aquarius";
break;
case 2: if(day < 20)
sign = "Aquarius";
else
sign = "Pices";
break;
case 3: if(day < 20)
sign = "Pices";
else
sign = "Aries";
break;
case 4: if(day < 20)
sign = "Aries";
else
sign = "Taurus";
break;
case 5: if(day < 21)
sign = "Taurus";
else
sign = "Gemini";
break;
case 6: if(day < 21)
sign = "Gemini";
else
sign = "Cancer";
break;
case 7: if(day < 23)
sign = "Cancer";
else
sign = "Leo";
break;
case 8: if(day < 23)
sign = "Leo";
else
sign = "Virgo";
break;
case 9: if(day < 23)
sign = "Virgo";
else
sign = "Libra";
break;
case 10:if(day < 23)
sign = "Libra";
else
sign = "Scorpio";
break;
case 11:if(day < 22)
sign = "Scorpio";
else
sign = "Sagittarius";
break;
case 12:if(day < 20)
sign = "Sagittarius";
else
sign = "Capricorn";
break;
}
System.out.println("The zodiac sign is: " + sign);
}
}
This program is just slightly more complex than the program for the Chinese zodiac. You still need to jump to 12 different cases (numbered 1-12 instead of 0-11), but additional day information is needed to pin down the sign.
4.4. Solution: Monty Hall
We now return to the Monty Hall simulation described at the beginning of
the chapter. Recall that objects of the Random
class allow us to generate all
kinds of random values. To implement this simulation successfully, our
program must make the decisions needed to set up the game for the
user as well as respond to the user’s input.
import java.util.*; (1)
public class MontyHall {
public static void main(String[] args) {
Random random = new Random();
int winner = random.nextInt(3); (2)
Scanner in = new Scanner( System.in );
System.out.print("Choose a door (enter 0, 1, or 2): ");
int choice = in.nextInt(); (3)
int alternative; (4)
int open;
| 1 | We begin with the import
statement needed to use both the Scanner and Random class
and then define the MontyHall class. |
| 2 | In the main() method we first decide which of the three doors is the
winner. To do so, we instantiate a Random object and use it to
generate a random number that is either 0, 1, or 2 by calling the
nextInt() method with an argument of 3 . We could have added 1 to
this value to get a random choice of 1, 2, or 3, but many counting
systems in computer science start with 0 instead of 1. We might as well
embrace it. |
| 3 | Next, we prompt the user to pick from the three doors and read the choice. |
| 4 | Finally, we declare two more int values to keep
track of which door to open and which door is the alternative that the
user can choose to change over to. |
Now, we have to navigate a complicated series of decisions.
if( choice == winner ) { (1)
int low;
int high;
if( choice == 0 ) { (2)
low = 1;
high = 2;
}
else if( choice == 1 ) {
low = 0;
high = 2;
}
else { //choice == 2
low = 0;
high = 1;
}
//randomly choose between other two doors
double threshold = random.nextDouble(); (3)
if( threshold < 0.5 ) { (4)
alternative = low;
open = high;
}
else { (5)
alternative = high;
open = low;
}
}
| 1 | In this segment of code, we tackle the possibility that the user happened to choose the winning door. To obey the rules of the game, we must randomly pick which of the two other doors to open. |
| 2 | First, we determine
which are the other two doors and save them in low and high ,
respectively. |
| 3 | Then, we generate a random number. |
| 4 | If the random number is less than 0.5, we keep the lower numbered door as an alternative choice for the user and open the higher numbered door. |
| 5 | If the random number is greater than or equal to 0.5, we do the opposite. |
else { (1)
alternative = winner;
if( choice == 0 ) { (2)
if( winner == 1 )
open = 2;
else
open = 1;
}
else if( choice == 1 ) {
if( winner == 0 )
open = 2;
else
open = 0;
}
else { //choice == 2
if( winner == 0 )
open = 1;
else
open = 0;
}
}
| 1 | This else block covers the case that the player did not pick the
winning door the first time. Unlike the previous code segment, we no
longer have a choice of which door to open. |
| 2 | Instead, we must always make the winner the alternative for the user to pick. Then, we simply determine which door is left over so that we can open it. |
Note that the
braces surrounding the blocks for each of the braces surrounding the
blocks for each of the three possible values of choice
are not
necessary but are included for readability.
System.out.println("We have opened Door " + open + (1)
", and there is junk behind it!");
System.out.print("Do you want to change to Door " + (2)
alternative + " from Door " + choice +
"? (Enter 'y' or 'n'): ");
String change = in.next();
if( change.equals("y") )
choice = alternative;
System.out.println("You chose Door " + choice);
if( choice == winner ) (3)
System.out.println("You win a pile of gold!");
else
System.out.println("You win a pile of junk.");
}
}
| 1 | This final segment of code informs the user which door has been opened. |
| 2 | It prompts the user to change his or her decision. |
| 3 | Depending on the final choice, the program says whether or not the user wins gold or junk. |
4.5. Concurrency: Selection
Selection statements (if
and switch
) seem to have
little to do with concurrency or parallelism. Selection allows you to
choose between alternatives while concurrency is about the interaction
between different threads of execution. As it turns out, there are two
reasons why selection and concurrency are deeply related to each other.
The first reason is that selection is one of the most basic tools in
Java. It’s impossible to go more than a few lines of a code without
encountering a selection statement, usually an if
.
Concurrent programs are not exempt from this dependence on if
statements. Making decisions is at the heart of all programming
languages running on all computers.
The second, more troubling reason is related to a problem with
some concurrent programs called a race condition, which is discussed
in detail in Chapter 14. Remember, one of
the biggest challenges of programming a computer is thinking in a
completely sequential and logical way. Each line of code is executed one
after the other. Adding in if
statements means that some code is
executed only if a condition is true and skipped otherwise. Consider the
following fragment of code:
if(!matches.areLit() && !flyingSparks) {
storageRoom.enter();
dynamite.unpack();
}
In this if
statement, an imaginary agent only enters the storage room
and unpacks the dynamite if the matches are not lit and there are no
flying sparks. When execution reaches the first line inside the if
block, we are certain that matches.areLit()
returned false
and
flyingSparks
is false
. This is a one-time check. If the first thing
that happens inside the if
block is code that lights the matches, Java
will not jump out of the if
statement.
As always, the programmer is responsible for making an if
statement
that makes sense. It’s possible that entering the storage room or
unpacking the dynamite causes sparks to fly or matches to burst into
flames spontaneously, but it seems unlikely. If the storageRoom
and
dynamite
objects were written by other people, we would expect their
documentation to explain unusual side-effects of this kind. In a
sequential program, the programmer can be reasonably sure that it’s
safe to unpack the dynamite.
Consider another fragment of code:
matches.light();
flyingSparks = sparklers.light(matches);
This code appears to light the matches and then to use the lit matches to set
some sparklers on fire. Presumably, if the process was successful,
flyingSparks
will have the value true
. This code is reasonable and
potentially helpful. If you were celebrating the 4th of July or needed
to signal a passing helicopter to rescue you from a desert island,
lighting sparklers could be a great idea. This sparkler-lighting code
could occur before the dynamite-unpacking code or after it, but, in a sequential
program, the protection of the if
statement keeps our hero from being blown up if
she tries to unpack the dynamite with lit sparklers.
In a concurrent program, all bets are off. Another thread of execution
can be operating at the very same time. It’s as if our hero is trying to
unpack the dynamite while the villain is lighting sparklers and tossing
them into the storage room. If the thread of execution gets to the if
statement and makes sure that the matches aren’t lit and that there are
no flying sparks, it continues onward. If sparks start flying after that
check, it still continues onward, oblivious of the fact. Even though
this risk of explosion exists, it depends on the timing of the two (or
more) concurrent threads of execution. It might be possible to run a
program 1,000 times with no problem. But if the timing is wrong on the
1,001st time, BOOM!
At this point, you don’t need to worry about values inside your if
statements being changed by other segments of code, but that problem is
at the heart of why concurrent programming can be so difficult. Whether
or not you’re programming concurrently, it’s important to keep
in mind the assumptions your code makes and the way different parts of
your program interact with each other.
4.6. Exercises
Conceptual Problems
-
Given that x, y, and z are propositions in Boolean logic, make a truth table for the expression ¬(x ∧ ¬y) ⊕ ¬z.
-
What’s the value of the Boolean expression ¬( (T ⊕ F) ∧ ¬(F ∨ T) )?
-
The calculation to determine the leap year given in Example 4.1 uses three
if
statements and threeelse
statements. Write the leap year calculation using a singleif
and a singleelse
. Feel free to useboolean
connectors such as||
and&&
. -
The XOR operator (
^
) is useful for combiningboolean
values, but it can be replaced with a more commonly used relational operator in Java. Which one? -
De Morgan’s laws are the following, which show that the process of negating a clause changes an AND to an OR and vice versa.
¬(x ∧ y) = ¬x ∨ ¬y
¬(x ∨ y) = ¬x ∧ ¬yCreate truth tables to verify both of these statements.
-
Use De Morgan’s laws given above to rewrite the following statement in Java to an equivalent statement that contains no negations.
boolean value = !((x != 4) && (y < 2));
-
Consider the following fragment of code.
int x = 5; int y = 3; if(y > 10 && (x = 10) > 5) y++; System.out.println("x: " + x); System.out.println("y: " + y);
What’s the output? Is the output changed if the condition of the
if
statement is changed toy > 10 & (x = 10) > 5
? Why? -
Consider the following fragment of code.
int a = 7; if(a++ == 7) System.out.println("Seven"); else System.out.println("Not seven");
What’s the output? Is the output changed if the condition of the
if
statement is changed to++a == 7
? Why?
Note: It is generally wise to avoid increment, decrement, and assignment statements in the condition of anif
statement because of the confusion that can arise.
Programming Practice
-
Write programs that:
-
Read in two
double
values and print the larger of the two of them. -
Read in three
double
values and print the largest of the three out. Note: You should use nestedif
statements.
-
-
-
Read an
int
value from the user specifying a certain number of cents. Useif
statements to print out the name of the corresponding coin in U.S. currency according to the table below. If the value doesn’t match any coin, printno coin
.Cents Coin 1
penny
5
nickel
10
dime
25
quarter
50
half-dollar
100
dollar
-
Read a
String
value from the user that gives one of the 6 coin names given in the table above. Useif
statements to print out the corresponding number of cents for the input. If the name doesn’t many any coin, printunknown coin
.
-
-
Re-implement both parts from Exercise 4.10 using
switch
statements instead ofif
statements. -
Expand the program given in Example 4.5 to give the correct suffixes (always “th”) for numbers that end in 11, 12, and 13. Use the modulus operator to find the last two digits of the number. Using an
if
statement, aswitch
statement, or a combination, check for those three cases before going into the normal cases. -
At the bottom of Section 4.3.3, we use a
switch
statement to determine the location of various area codes in New York state. Write an equivalent fragment of code usingif
-else
statements instead. -
Every member of your secret club has an ID number. These ID numbers are between 1 and 1,000,000 and have two special characteristics: They are multiples of 7 and all end with a 3 in the one’s place. For example, 63 is the smallest such value, and 999,943 is the largest such value. Write a program that prompts the user for an
int
value, reads it in, and then says whether or not it could be used as an ID number. Note: You need to use the modulus operator in two different ways to test the value correctly. -
According to the North American Numbering Plan (NANP) used by the United States, Canada, and a number of smaller countries, a legal telephone number takes the form
XYY-XYY-YYYY
, whereX
is any digit 2-9 andY
is any digit 0-9. Write a program that reads in aString
from the user and verifies that it is a legal NANP phone number. The length of the entireString
must be 12. The fourth and eight characters in theString
(with indexes3
and7
) must be hyphens (-
), and all the remaining digits must be in the correct range. Use thecharAt()
method of theString
class to get thechar
value at each index. Note: There are several ways to structure theif
statements you need to use, but the number of conditions may become large. (23 or more!) -
Re-implement the solution to the Monty Hall program given in Section 4.4 using
JOptionPane
to generate GUIs for input and output.
5. Repetition
Q-Tip: You on point, Phife?
Phife Dawg: All the time, Tip.
Q-Tip: You on point, Phife?
Phife Dawg: All the time, Tip.
Q-Tip: You on point, Phife?
Phife Dawg: All the time, Tip.
Q-Tip: Well, then grab the microphone and let your words rip.
5.1. Problem: DNA searching
The world of bioinformatics is the intersection between biology and computer science. Sequencing genomes, determining the function of specific genes, the analysis and prediction of protein structures, and biomedical imaging are just a few of the areas under the umbrella of bioinformatics. Much fascinating research is being done in this area as biologists become better programmers and computer scientists apply their techniques to biology.
Because of its fundamental importance and the incredible amount of information involved, with tens or hundreds of millions of base pairs of DNA in each human chromosome, DNA is a central focus of bioinformatics. As you may know, a DNA strand is made up of a sequence of four nucleotide bases: adenine, cytosine, guanine, and thymine. These bases are usually abbreviated as A, C, G, and T, respectively.
Searching for a specific DNA subsequence within a larger sequence is a common task for biologists to perform. Your goal is to write a program that will search for a subsequence and report how many times it was found within the sequence. For example, if you are given the sequence ATTAGACCATATA and asked to search for CAT, your program should output 1, since there is exactly 1 occurrence of CAT within ATTAGACCATATA. One feature of this problem that makes it more interesting is that occurrences can overlap. For example, given the sequence TATTATTAGATTA and asked to search for TATTA, the correct answer is 2. The sequence begins with a TATTA, but the third T in the sequence is also the first T in a second instance of TATTA.
In Chapter 4, you learned tools that allow you to do
comparisons and make choices based on the results. These tools will
become even more useful. For example, when you come across a char
in a
sequence, you know how to compare it to a char
in the subsequence you
are searching for. The tools you do not yet have are those that allow
repetition. Because this problem requires the program to process a DNA
sequence of arbitrary length, we will need some way to perform an
action repeatedly.
5.2. Concepts: Repetition
You now know how to write choices into a Java program, but so far, each choice can only be made once. So if you want the computer to do a lot of things, you have to type a lot of things. One of the big disadvantages of computers is that they have no intelligence: They can follow instructions blindly, but they can’t do anything else. One of the big advantages of computers is that they’re fast.  To take advantage of this speed, we need to give computers instructions to perform tasks over and over. Such an instruction must have two components to be useful: It must have a way to change the task slightly each time so that each task accomplishes something different. It must also have a way to decide when to stop, otherwise it will continue forever.
The first component is the more subtle one. Crafting a set of instructions so that each repetition of the task is appropriate will be different for every problem. The second component is easier to describe: We’re going to rely on Boolean logic, just as we did for conditional statements. The main tool for repetition in Java and many other languages is called a loop. The body of a loop contains the task to be performed. The rest of the loop, at the very least, contains a condition. Every time the task given in the body of the loop completes, the computer will check the condition. If the condition is true, it’ll do the task again. If the condition is false, the computer is done with the loop and can move on to the code that comes afterward.
One of the difficulties of programming a computer is that we must be very explicit. Even the most obvious tasks must be spelled out in meticulous detail. Let’s consider a simple task, one that we perform every day. If we’re in a room and we want to leave, we simply walk out the nearest door. Assuming there is only one door in the room, how can we describe this process by breaking it down into the steps we (literally) take? Perhaps we could say the following.
Walk toward the door until you reach it.
This statement is a little more specific than Leave the room, but it doesn’t conform nicely to the paradigm of a loop, that is, a clearly separated task and a condition. The following is better.
While you’re not at the door,
take a step toward the door.
Now we have good separation between the work done and the condition for repeating. What’s the task performed in the body of this loop, and what’s the condition? The task is taking a step toward the door. The condition is not being at the door. It seems a little awkward to include that “not,” but in our definition of loops, the body is executed as long as the condition is true.
In a loop, we call each execution of the body of the loop an iteration. When we say that a program iterates over the statements in a loop, we are referring to a single pass through the body of a loop. In this case, the loop will iterate however many times there are steps to the door from the starting position. It is even possible that the loop will iterate zero times: The person following this set of instructions might already be at the door!
It’s hard to get away from numbers in a computer program, especially since everything is fundamentally stored as numbers inside of a computer. So, the most common kind of loop is one that iterates a fixed number of times. For example, your morning exercise routine might include jumping rope 100 times. We could formulate a loop to do that like so.
Set your counter to 0.
While your counter is less than 100,
jump rope.
Increase your counter by 1.
This loop requires set up to start the counter at the right value. Then, the work done by the loop is the actual rope jumping and the counter increment. The condition is the counter being less than 100. Note that this is strictly less than 100. After the first jump, the counter will be incremented to 1. After the 100th jump, the counter will be incremented to 100. Since 100 is not less than 100, the loop will exit. If the condition was the counter being less than or equal to 100, the person following the instructions would jump 101 times.
Input can also be a factor in loop repetitions. For example, you might
be a soldier training in the U.S. Marine Corps. Perhaps your drill
sergeant has commanded you to do push-ups until he says you can stop. We
might formulate a loop to do this as follows.
Do:
Push-up.
Ask the drill sergeant if you can stop.
While the answer is “no.”
As is the case with user input, you must often go into the loop at least once to get the input. This loop requires the soldier to do at least one push-up before asking to stop. Some systems might use input but have other constraints. A more realistic version of this loop might be the following.
Do:
Push-up.
Ask the drill sergeant if you can stop.
While the answer is “no” and you haven’t collapsed.
Remember, the condition for a loop should be a Boolean, and the loop runs as long as the condition is true. However, there is no reason why the Boolean can’t be a complicated expression using all the Boolean logic we have come to know and love.
It’s also possible to nest loops. Nesting loops means putting one loop inside of another, similar to the way that conditional statements could be nested inside of other conditional statements. Just like any other statement, an inner loop will be run as many times as the outer loop runs. Of course, the statements inside of the inner loop will be run according to the conditions of that loop. So, if an outer loop runs 10 times and an inner loop runs 50 times, a statement in the body of an inner loop would run 500 times!
As an example, if you’re working out, you might do several sets of
bench presses with a fixed number of reps in each set. If you did 3 sets
of 15 bench presses each, your workout program might look like this:
Set your set counter to 0.
While your set counter is less than 3,
set your rep counter to 0.
While your rep counter is less than 15,
do a bench press.
Increase your rep counter by 1.
Rest for 2 minutes.
Increase your set counter.
This way of describing the workout program seems tedious. Most of the description is structural: conditions for the loops and increments for the counters. The only “real” activities are the bench press and the resting. As you can see, the bench press is inside the inner rep loop and will be executed 15 times for each complete execution of the inner rep loop. Since the inner rep loop sits inside the outer set loop, it’ll be executed 3 times, giving a grand total of 45 bench presses. Resting, however, is after the inner rep loop but still contained in the outer set loop and will be executed 3 times, totaling 6 minutes of rest.
As with conditionals, writing out loops in English is tedious and imprecise. In the next section, we’ll discuss the tools for writing loops in Java. Because Java was designed with loops as a central tool, we can write loops more succinctly than in English, squeezing a lot of information into a small space. Because we pack so much information into them, loops can look daunting at first. Remember that the syntax we’ll introduce is only the formal Java way of expressing a condition and a list of instructions to execute repeatedly.
5.3. Syntax: Loops in Java
The Java programming language contains three differently named kinds of
loops: while
loops, for
loops, and do
-while
loops. All of them
allow you to write code that will be executed repeatedly. In fact, any
program that uses one kind of loop to solve a problem could be
converted to use either of the other two kinds. The three kinds are
provided in Java partly so that it’s easy to code certain typical forms
of repetition and partly because the C language, an ancestor of Java,
contained these three. We’ll begin by describing while
loops because
they have the simplest form and then move on to the other two kinds. We’ll
then explain the syntax for nesting together multiple loops and
finally discuss several of the common pitfalls encountered by
programmers when coding loops.
5.3.1. while
loops
Superficially, the syntax of a while
loop resembles an if
statement.
It starts with the keyword while
followed by a boolean
condition in
parentheses with a block of code surrounded by braces ({ }
)
afterward. This similarity is not accidental. The only difference
between the two is that the body of the if
statement will run a only
single time, while the body of the while
loop will run as long as the
condition remains true
. Figure 5.1 shows the pattern of
execution for while
loops.
true
, all of the statements in the body of the loop are executed, and then the condition is checked again. When the check is false
, execution skips past the body of the loop.If we assume that the boolean
value atDoor
says whether or not we
have reached the door and the method walkTowardsDoor()
allows us to
take one step closer to the door, we could formulate our example from
the beginning of the previous section as follows.
while(!atDoor) {
atDoor = walkTowardsDoor();
}
Here we assume that the walkTowardsDoor()
method gives back a
boolean
value that is true
if we have reached the door and false
otherwise. Unless the walkTowardsDoor()
method is able to change the
value of atDoor
, the loop will repeat forever, a phenomenon known as
an infinite loop.
while(true) {
System.out.println("Help me!");
}
This code gives an example of an infinite loop. If you run this code inside
of a program, it’ll print out an endless succession of Help me!
messages. Be prepared to stop the program by typing Ctrl+C
(hold down
the Control
key and press C
) because it won’t end otherwise. Not
all infinite loops are this obvious. A programmer will not usually use
true
as the condition of a loop, but doing so is not always wrong.
Some loops are expected to continue for quite some time with no definite
end. To leave a loop abruptly, you can use the break
command.
while(true) {
System.out.println("Help me!");
break;
}
This loop will only print out a single Help me!
before exiting. A
break
command can be used with an if
statement to make a loop that
repeats more than once.
int counter = 0;
while(true) {
System.out.print("the loop ");
counter++;
if(counter >= 3)
break;
}
System.out.println("is on fire!");
This loop will print out the loop the loop the loop is on fire!
Of
course, the break
statement unnecessarily complicates the code. We
could have written equivalent code as follows.
int counter = 0;
while(counter < 3) {
System.out.print("the loop ");
counter++;
}
System.out.println("is on fire!");
Now, we move on to a more complicated example that can print out the binary representation of a number.
As we discussed in Chapter 1, binary numbers
are the building blocks of every piece of data inside a modern
computer’s memory. Integers are stored in binary. The representation of
floating-point numbers is more complicated, but it also uses 1s and 0s.
Even the char
data type and the String
values built from them are
fundamentally stored as binary numbers. For this reason, computer
scientists tend to be familiar with the base 2 number system and how to
convert between it and base 10, our usual number system.
In base 10, the number 379 is equal to 3 · 100 + 7 · 10 + 9 · 1 = 3 · 102 + 7 · 101 + 9 · 100. Moving from right to left, the value of each place increases by a factor of 10. A binary number is the same, except that the increase is by a factor of 2 and no single digit is greater than 1. Thus, the number 1010112 = 1 · 25 + 0 · 24 + 1 · 23 + 0 · 22 + 1 · 2 + 1 · 20 = 1 · 32 + 0 · 16 + 1 · 8 + 0 · 4 + 1 · 2 + 1 · 0 = 43. In binary, the number 379 =<PHONE_NUMBER>.
To convert a number n to binary, we first find the largest power of 2 that is not larger than n. Then, we begin a repetitive process that stops when the power of 2 under consideration is 0. If 2 raised to the current power is bigger than n, we print out a 0 because that power is too big for n. Otherwise, we print out a 1, subtract 2 raised to that power from n, and move on to the next smaller power of 2. This process will print a 0 for every power of 2 that’s not in n and a 1 for every one that is, giving exactly the definition of a number written in base 2.
import java.util.*;
public class DecimalToBinary {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a base 10 number: ");
int number = in.nextInt();
int power = 1;
while(power <= number/2)
power *= 2;
while(power > 0) {
if(power > number)
System.out.print(0);
else {
System.out.print(1);
number -= power;
}
power /= 2;
}
}
}
The first while
loop in this program doubles the value of power
until doubling it again would make it larger than number
. We go up to
and including number/2
, otherwise we’d stop when power
was
larger than number
. After that loop, we begin repeatedly checking to
see if a given power of 2 is bigger than the value left in number
. If
it is, we know that we do not use that power. If it’s not, we do and
must remove that power from the value of number
.
You may have been tempted to solve this problem by determining if a
given number is even or odd. If it’s even, then you record a 0, and if
it’s odd, then you record a 1. You could then divide the number by two
and repeat the process of determining whether it is even or odd. You
would continue this process until the number became 0. This procedure
requires only a single while
loop and would give the digits of the
number in base 2. Unfortunately, you would get the digits in reverse
order. Because we write our numbers with the most significant digit on
the left, we had to use the code given above to first find the largest
value and work backward, in order to determine the binary digits in the
correct sequence.
5.3.2. for
loops
Let’s return to our code that prints out
the loop the loop the loop is on fire!
int counter = 0;
while(counter < 3) {
System.out.print("the loop ");
counter++;
}
System.out.println("is on fire!");
This code involves some initialization, a condition, and an update, as
many loops do. The initialization sets counter
to 0
, the condition
checks to make sure that counter
is less than 3
, and the update
increments counter
by 1 every iteration of the loop. These three
elements are so common that a special kind of loop called the for
loop
was designed with them explicitly in mind. Most for
loops are
dependent on a single counting variable. To make the loop easy to read,
the initialization, condition, and update, all of which relate to this
variable, are pulled into the header of the loop. We could code the
previous while
loop example more cleanly, using a for
loop, as
follows.
for(int i = 0; i < 3; i++) {
System.out.print("the loop ");
}
System.out.println("is on fire!");
The header of a for
loop consists of those three parts: the
initialization, the condition, and the update, all separated by
semicolons. Figure 5.2 shows the pattern of execution for
for
loops.
true
, all of the statements in the body of the loop are executed, followed by the increment step. Then the condition is checked again. When the check is false
, execution skips past the body of the loop.You may have noticed that we changed the variable name used within
the loop from counter
to i
. Doing so doesn’t change the function of
the code. We did so because using the variables i
, j
, and sometimes
k
is a very common practice with for
loops. By using variables named
like this, we are indicating that the variable is just a dummy counter
that we are using to make the loop work, not some variable with a
grander purpose. Also, with three uses of a single variable in the
header of a for
loop, a long variable name takes up a lot of space.
for
loops are used in Java programs more than the other two loops.
They work well when you know how many times you want to iterate through
the loop, which you often do. You can think of the first part of the
for
loop header as the starting point, the second part as the ending
point, and the third part as how you get from the start to the end. Many
beginning programmers get stuck on the idea that every for
loop starts
with int i = 0
and ends with i++
. While this pattern is often true,
there are many other ways to use a for loop. For example, we could print
the powers of 2 that are less than 1000.
for(int i = 1; i < 1000; i *= 2) {
System.out.println(i);
}
This segment of code prints out 1
, 2
, 4
, 8
, 16
, 32
, 64
,
128
, 256
, and 512
on separate lines, which are the powers of
2 from 20 up to 29.
Both of the examples of for
loops we
have given have only had a single executable line in the body of the
loop. Like if
statements, loops only require braces if their bodies
have more than one executable line. Many of the while
loops from the
previous subsection could have been written without braces.
Just because a for
loop already has a counting mechanism doesn’t mean
that we won’t need other variables to perform useful tasks. For
example, given a String
, we could try to find the letter of the
alphabet in the String
which is closest to the end of the alphabet.
For the String
"Pluto is no longer a planet"
, the latest letter in
the alphabet is 'u'
. To write code that will do this job, we must use
the counting variable from the for
loop as an index into the
String
. Then, we must also have a temporary variable where we keep the
latest letter found so far. To get the ith char
from a
String
, we can use the charAt()
method. Recall that the index of the first
char
in a String
is 0, and the index of the last char
is one less
than the length of the String
.
String s = "The quick brown fox jumps over the lazy dog.";
String lower = s.toLowerCase();
char latest = ' ';
char c;
for(int i = 0; i < lower.length(); i++) {
c = lower.charAt(i);
if(c >= 'a' && c <= 'z' && c > latest)
latest = c;
}
System.out.println("The latest character in the alphabet from your message is: '"
+ latest + "'.");
The first thing we do in this example is convert s
to lowercase, so
that we are comparing all char
values in the same case. Next, we run
through lower
, starting at index 0 and going until we reach the end of
the String
. For each char
, we check to see if it is an alphabetic
character and then if it is later in the alphabet than our current
latest. If it is, we store it into latest
. After the loop, we print
out the value in latest
. We have chosen the char
' '
because it is
numerically earlier than all the letters in the alphabet. If the output
is a space, we’d know that none of the characters in s
were
alphabetic.
For the example given, the latest character in the alphabet is 'z'
because of the word "lazy"
. One weakness in this code is that it will
always search through the entire String
, even if the letter 'z'
has
already been found. For the String
"The quick brown fox jumps over the lazy dog."
, we’re not wasting too
much time. However, if the String
were "Zanzibar!"
followed by the
full text of War and Peace, we’d be wasting thousands and
thousands of operations reading characters when we knew that 'z'
was
going to be the latest letter, no matter what. We can rewrite our
for
loop so that it quits early if it reaches a 'z'
.
for(int i = 0; i < lower.length(); i++) {
c = lower.charAt(i);
if(c >= 'a' && c <= 'z' && c > latest)
latest = c;
if(latest == 'z')
break;
}
This version of the for
loop will break out immediately if the latest
is already a 'z'
. This code will work efficiently, but many
professional programmers discourage the use of break
except when
absolutely necessary (like in a switch
statement). If a break
is
used to exit the loop, this logic can be encoded into the condition of
the loop. Thus, the same loop written with better style would be the
following.
for(int i = 0; i < lower.length() && latest != 'z'; i++) {
c = lower.charAt(i);
if(c >= 'a' && c <= 'z' && c > latest)
latest = c;
}
For this final version of the loop, we have made the conditional portion
of the header more complex. The comparison using <
gives a boolean
that we combine using &&
with the boolean
from the comparison
using !=
. As always, remember that the loop will continue iterating as
long as the condition is true
. Since we need both parts of the
condition to be true
to continue executing, we use the &&
operator
to connect them.
We apologize to international readers for focusing on the Latin alphabet
used by English and many other Western European languages. It should be
possible to make a localized version of this example with any alphabet
by checking the return value of Character.isLetter(c)
, which is valid
for all single-character Unicode values, although the idea of
alphabetical order doesn’t really apply to some character systems like
the hanzi and kanji of Chinese and Japanese. Regardless, using the
Character.isLetter()
method is recommended for almost all
applications, since it’s more general and more readable.
Prime numbers are integers greater than 1 whose only factors are 1 and themselves. If you’ve encountered prime numbers before, they probably seemed like a mathematical curiosity and nothing more. In fact, prime numbers are the basis of a very practical application of mathematics: cryptography. With the use of some math and very large prime numbers, computer scientists have devised techniques that make messages sent over the Internet more secure.
These techniques are beyond the scope of this book, but we can at least write some code to determine if a number n is prime. To do so, we can simply divide n by all the numbers between 2 and n - 1. If none of the numbers divide it evenly, it must be prime. Here is this basic solution.
import java.util.*;
public class PrimalityTester0 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a number: ");
long number = in.nextLong();
boolean prime = true;
for(long i = 2; i < number && prime; i++)
if(number % i == 0)
prime = false;
if(prime)
System.out.println(number + " is prime.");
else
System.out.println(number + " is not prime.");
}
}
This program has a for
loop that runs from 2
up to number - 1
,
provided that we don’t find a number that evenly divides number
. This
optimization means that the program will output the moment that it knows
that the number is not prime, but we’ll have to wait for it to
check all the other possibilities before it is sure that the number is
prime.
One insight that we can use to make the program more efficient is that, after checking 2, we don’t have to divide it by any even numbers. So, we can do half the checking with a few simple modifications.
import java.util.*;
public class PrimalityTester1 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a number: ");
long number = in.nextLong();
boolean prime = number == 2 || number % 2 != 0;
for(long i = 3; i < number && prime; i += 2 )
if(number % i == 0)
prime = false;
if(prime)
System.out.println(number + " is prime.");
else
System.out.println(number + " is not prime.");
}
}
This version of the program sets the boolean
variable prime
to
false
if number
is divisible by 2 (unless it’s 2 itself) and true
otherwise. Then, it
starts the search at 3 and continues in jumps of 2. Although we save half the checks,
we can do much better. Note that if a number n is divisible by 2, then it’s also divisible by
n/2. So, if a number is not divisible by 2, it’s also not divisible by any
number larger than n/2. If it’s not divisible by 2 or 3, then it’s also not divisible by any number
larger than n/3. If it’s not divisible by 2 or 3
or 4, it’s not divisible by any number larger than
n/4, and so on. Thus, we don’t have to check all
the way up to n - 1. If we’re checking to see if
n is divisible by x and learning that
n is not divisible by anything larger than
n/x, the point where x = n/x
is as follows.
Thus, we only need to search up to the square root of n, which will save much more time.
import java.util.*;
public class PrimalityTester2 {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a number: ");
long number = in.nextLong();
boolean prime = number == 2 || number % 2 != 0;
long root = (long)Math.sqrt(number);
for(long i = 3; i <= root && prime; i += 2 )
if(number % i == 0)
prime = false;
if(prime)
System.out.println(number + " is prime.");
else
System.out.println(number + " is not prime.");
}
}
Note in this version of the program we do go up to and including root
,
because there’s the possibility that number
is a perfect square.
DNA is usually double stranded, with each base paired to another specific base, called its complementary base. The following table shows the association between each base and its complementary base.
| Base | Abbreviation | Complementary Base |
|---|---|---|
Adenine |
A |
T |
Cytosine |
C |
G |
Guanine |
G |
C |
Thymine |
T |
A |
A simple but common task is finding the reverse complement of a DNA sequence. The reverse complement of a DNA sequence is its sequence of complementary bases given in reverse order. For example, the reverse complement of ACATGAG is CTCATGT. This sequence is found by first finding the complement of ACATGAG, which is TGTACTC, and then reversing its order.
We’ll write a program that finds the reverse complement of a DNA
sequence entered by a user. This sequence will be entered as a sequence
of characters made up of the four abbreviations for the bases: A, C, G,
and T. We’ll store this sequence as a String
and perform some
manipulations on it to get the reverse complement.
import java.util.*;
public class ReverseComplement {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a DNA sequence: ");
String sequence = in.next().toUpperCase();
String complement = "";
for(int i = 0; i < sequence.length(); i++) (1)
switch(sequence.charAt(i)) { //get complements
case 'A': complement += "T"; break;
case 'C': complement += "G"; break;
case 'G': complement += "C"; break;
case 'T': complement += "A"; break;
}
String reverseComplement = "";
//reverse the complement
for(int i = complement.length() - 1; i >= 0; i--) (2)
reverseComplement += complement.charAt(i);
System.out.println("Reverse complement: " + reverseComplement);
}
}
| 1 | This example first creates a String filled with the complement of the
base pairs from the input String . |
| 2 | Then, it creates a
new String that is the reverse of the complement sequence. |
Note how
complement
is created by appending the char
corresponding to the
complementary base at the end of complement
. If we inserted each
char
at the beginning of complement
, we wouldn’t need to reverse in
a separate step.
import java.util.*;
public class CleverReverseComplement {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Please enter a DNA sequence: ");
String sequence = in.next().toUpperCase();
String reverseComplement = "";
for(int i = 0; i < sequence.length(); i++)
switch(sequence.charAt(i)) { //get complements
case 'A': reverseComplement = "T" + reverseComplement; break;
case 'C': reverseComplement = "G" + reverseComplement; break;
case 'G': reverseComplement = "C" + reverseComplement; break;
case 'T': reverseComplement = "A" + reverseComplement; break;
}
System.out.println("Reverse complement: " + reverseComplement);
}
}
5.3.3. do
-while
loops
Use this rule of thumb for deciding which kind of loop to use: If you
know how many times you want the loop to execute, use a for
loop. If
you don’t know how many times you want it to execute, use a while
loop. Clearly, this rule is not iron-clad. In the previous example, we
used a for
loop even though it would stop executing as soon as a 'z'
was encountered. Nevertheless, it seems like we have covered all of the
possible situations with while
and for
loops. When should we use
do
-while
loops? The simple answer is: never.
You never have to use a do
-while
loop. With a little bit of effort,
you could use a single kind of loop for every job. The key difference between
a do
-while
loop and a regular while
loop is that a do
-while
loop
will always run at least once. Neither of the other two loops give you
that guarantee. The syntax for a do
-while
loop is a do
at the top of
a loop body enclosed in braces, with a normal while
header at the end,
including a condition in parentheses, followed by a semicolon.
Figure 5.3 shows the pattern of execution for do
-while
loops.
false
, execution skips past the body of the loop. A do
-while
loop is guaranteed to run at least once.We can use a do
-while
loop to print out the first 10 perfect squares
as follows.
int x = 1;
do {
System.out.println(x*x);
x++;
} while(x <= 10);
This loop behaves exactly the same as the following loop.
int x = 1;
while(x <= 10) {
System.out.println(x*x);
x++;
}
The time when a do
-while
loop is really going to shine is when your
program will work incorrectly if the loop doesn’t run at least once.
This situation often occurs with input, when the loop must run at least
once before checking the condition. For example, imagine that you want
to write a program that picks a random number between 1 and 100 and lets
the user guess what it is until the user gets it right. You need a loop
because it’s a repetitive activity, but you need to let the user guess
at least once so that you can check if he or she was right. The
following program fragment does exactly that.
Scanner in = new Scanner(System.in);
Random random = new Random();
int guess;
int number = random.nextInt(100) + 1;
do {
System.out.print("What's your guess? ");
guess = in.nextInt();
} while(guess != number);
System.out.println("You got it! The number was " + number + ".");
You could perform the same function with a while
loop, but you’d
need to get input from the user before the loop starts. Using the
do
-while
loop is a little more elegant.
5.3.4. Nested loops
Just as you can nest if
statements, it’s possible to nest loops inside of other
loops. In the simplest case, you may have some repetitive activity that
itself needs to be performed several times. For example, when you were
younger, you probably had to learn your multiplication tables. For each
number, a multiplication table gave the value of the product of that
number by every integer between 1 and 12. We can write code to print out
out the multiplication table for every number from 1 to 10 by simply
repeating the process.
for(int number = 1; number <= 10; number++) {
for(int factor = 1; factor <= 12; factor++) {
System.out.println(number + " x " + factor +
" = " + number*factor);
}
System.out.println();
}
The outer loop incrementing number
runs 10 times. The inner loop
incrementing factor
will run 12 times for each iteration of the outer
loop. Thus, the code in the inner loop will run a total of 120 times.
Every 12 iterations, the inner loop will stop, and an extra blank line
will be added by the System.out.println()
method in the outer loop.
The sequence consisting of 1, 3, 6, 10, 15, and so on is known as the triangular numbers. The ith triangular number is the sum of the first i integers. They are called triangular numbers because they can be drawn as equilateral triangles in a very natural way, if you use a number of dots equal to the number.
We can use nested loops to print out the first n triangular numbers, where n is specified by the user.
import java.util.*;
public class TriangularNumbers {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("How many triangular numbers? ");
int n = in.nextInt();
int sum;
for(int i = 1; i <= n; i++) {
sum = 0;
for(int j = 1; j <= i; j++)
sum += j;
System.out.println(sum);
}
}
}
As you can see, the outer loop iterates through each of the n
different triangular numbers. Then, the inner loop does the summation
needed to compute the given triangular number. However, producing a sequence of
triangular numbers this way is inefficient. Nested loops are an effective way to solve many problems,
particularly certain types of problems using arrays, but we can generate
triangular numbers using only a single for
loop. The key insight is
that we can keep track of the previous triangular number and add
i to it, as i increases.
import java.util.*;
public class CleverTriangularNumbers {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("How many triangular numbers? ");
int n = in.nextInt();
int triangular = 0;
for(int i = 1; i <= n; i++) {
triangular += i;
System.out.println(triangular);
}
}
}
By removing the inner for
loop, the total amount of work needed is
greatly reduced.
5.3.5. Common pitfalls
With great power comes great responsibility. The power to repeat things a large number of times means that we can also repeat our mistakes a large number of times. Many classic bugs occur as a result of logical or typographical errors in loops. We list a few of the most common below.
|
Pitfall: Infinite loops
It’s possible to create a loop that never terminates. Your program may take a long time to finish, but if it takes much longer than you expect, an infinite loop might be the culprit. Infinite loops might occur because you forgot to include an appropriate statement to advance a counter.
This code is presumably intended to print out the first 100 integers,
but there’s no code that increases the value of
One might expect this code to print out 20 lines of output. However,
remember that |
|
Pitfall: Almost infinite loops
Many loops are truly infinite; others take a really long time. For example, if you intended to run a loop down from 10 to 0, but increment your counter instead of decrementing it, overflow means that you will eventually get to a number less than 0, but it will take more than 2 billion increments instead of the expected 10 decrements.
This loop will significantly slow your code. Everyone will be so tired of waiting that they might leave the rocket launch. Of course, another problem with almost infinite loops is that you are dealing with the wrong values. No one expects to hear the number 2,147,483,647 in a countdown. |
|
Pitfall: Fencepost errors
Perhaps the most common loop errors are fencepost errors, often known as off-by-one errors. The name “fencepost” comes from a related mistake that someone might make when putting up a fence. Imagine that you want to erect a 10 meter long chain link fence with a support post every meter, how many posts do you need? In fact, we haven’t given you enough information to answer the question correctly. If your fence is built in a straight line, you’ll need 11 posts so that you have a post at each end. However, if your fence is a rectangular enclosure, say 3 meters by 2 meters, you’ll only need 10 posts. In loops, fencepost errors are often due to zero-based counting. A
Of course, sometimes we need one-based counting instead. After being used to zero-based counting, a programmer might make the following loop that incorrectly iterates 9 times.
The correct version that iterates 10 times is below.
If you want to iterate n times, start at 0 and go up to
but not including n or alternately start at 1 and go up to and
including n. To keep loop headers consistent, some
programmers always start at 0 and then adjust the values inside the
loop, printing out |
|
Pitfall: Skipped loops
A loop runs as long as its condition is For example, we can write a program that will add any number of positive values. When the user is finished using the adder, he or she enters a negative number. This negative number, called a sentinel value, tells the program to stop executing the loop. Below is an incorrect implementation of such a program.
This loop will never be executed because |
|
Pitfall: Misplaced semicolons
The idea of a statement in Java is often amorphous in the minds of beginning programmers. An entire loop (with any number of loops nested inside of it) is considered one statement. An executable statement ending with a semicolon is one statement as well, even when that executable statement is empty. Thus, the following is a legal (but infinite) loop.
This code was supposed to count down from 100, just like in the game of
Hide and Seek; however, there is a semicolon after the condition of the
This error is common especially for those new to loops and conditional
statements and are in the habit of putting semicolons after everything.
A misplaced semicolon doesn’t always result in an infinite loop. Here
is the
This version of the code will execute similarly, except the decrement is
built into the header of the loop. So, the loop will execute the empty
statement, but it will also decrement There are some cases when an empty statement for a loop body is useful although it is never necessary. In future chapters, we’ll point out situations in which you may wish to use an empty statement this way. |
5.4. Solution: DNA searching
Below we give a solution to the DNA searching problem posed at the
beginning of the second half of this chapter. Our solution prints out
the index within the sequence when it finds a match with the
subsequence it’s looking for. Afterward, it prints out the total number of
matches. Our code also does error checking to make sure that the user
only enters valid DNA sequences containing the letters A, C, G, and T.
We begin our code with the standard import
statement and class
definition.
import java.util.*;
public class DNASearch {
public static void main(String[] args) {
Scanner in = new Scanner(System.in); (1)
String sequence, subsequence;
boolean valid; (2)
char c;
| 1 | The main() method instantiates a Scanner object and declares both of
the String variables we’ll need to store the DNA sequences. |
| 2 | The method
also declares a boolean and a char we’ll use for input checking. |
do {
System.out.print("Enter the DNA sequence you wish to search in: "); (1)
sequence = in.next().toUpperCase(); (2)
valid = true;
for(int i = 0; i < sequence.length() && valid; i++) { (3)
c = sequence.charAt(i);
if(c != 'A' && c != 'C' && c != 'G' && c != 'T') { (4)
System.out.println("Invalid DNA sequence!");
valid = false;
}
}
} while(!valid); (5)
| 1 | Next, the user is prompted for a DNA sequence to search in. |
| 2 | This
String stored in sequence is converted to uppercase just in case
the user is not being consistent. |
| 3 | The inner for loop in this code checks each char inside of sequence . |
| 4 | If any char is not an
'A' , 'C' , 'G' , or 'T' , then valid is set to false . As a
result, the for loop terminates. Also, the do -while loop repeats the
prompt and gets a new String for sequence from the user. |
| 5 | This outer
do -while loop continues as long as the user keeps entering invalid DNA
sequences. |
do {
System.out.print("Enter the subsequence you wish to search for: ");
subsequence = in.next().toUpperCase();
valid = true;
for(int i = 0; i < subsequence.length() && valid; i++) {
c = subsequence.charAt(i);
if(c != 'A' && c != 'C' && c != 'G' && c != 'T') {
System.out.println("Invalid DNA sequence!");
valid = false;
}
}
} while(!valid);
The code used to input subsequence
while doing error checking is
virtually identical to the code to input sequence
.
int found = 0;
for(int i = 0; i < sequence.length() - subsequence.length() + 1; i++) { (1)
for(int j = 0; j < subsequence.length(); j++) { (2)
if(subsequence.charAt(j) != sequence.charAt(i + j)) (3)
break;
if(j == subsequence.length() - 1) { //matches (4)
System.out.println("Match found at index " + i);
found++;
}
}
}
| 1 | The workhorse of the search is found in these nested for loops.
The outer loop iterates through every index in sequence , until it
comes to an index that is too late to be the start of a new subsequence
(since the subsequence would be too long to fit anymore). This happens
to be when the value of i is greater than or equal to
sequence.length() - subsequence.length() + 1 . It may take some thought
to verify that this condition is the correct one. One way to think about
this problem is by noting that, when sequence and subsequence have
the same length, you need to check starting at index 0 of sequence
but not any later indexes. Also, if subsequence is one char longer
than sequence , there can never be a match. In that case, the value of
sequence.length() - subsequence.length() + 1 would be 0 . Since 0
is not less than 0 , the outer for loop would never execute. |
| 2 | The inner for loop iterates through the length of subsequence ,
making sure that every char in sequence , starting at the appropriate
offset, exactly matches a char in subsequence . |
| 3 | If, at any point, the
two char values do not match, the inner for loop will immediately
exit, using the break command. |
| 4 | However, on the last iteration of the
inner for loop, when j is one less than the length of subsequence ,
we know that all of subsequence matched a part of sequence . As a
result, we print out the index of sequence where subsequence started
and increment the found counter. |
If you know the String
class well, you can use the indexOf()
method
to replace the inner for
loop. We leave that approach as an exercise.
Finally, we print out the total number of matches found. In order to
avoid awkward output like 1 matches found.
, we used an if
-else
to
customize the output based on the value of found
.
if(found == 1)
System.out.println("One match found.");
else
System.out.println(found + " matches found.");
}
}
The ideas needed to correctly implement the solution are not difficult, but catching all the off-by-one errors and getting every detail right takes care. There’s also more than one way to code this solution. For example, we could have written the nested loops that do the searching as follows.
int found = 0;
for(int i = 0; i < sequence.length() - subsequence.length() + 1; i++) {
for(int j = 0; j < subsequence.length() &&
subsequence.charAt(j) == sequence.charAt(i + j); j++)
if(j == subsequence.length() - 1) { // Matches
System.out.println("Match found at index " + i);
found++;
}
}
}
This design is preferred by many since it removes the break
. By using
an empty statement, it’s possible to move the check to see if the
matching process is done outside of the inner for
loop.
int found = 0;
int j;
for(int i = 0; i < sequence.length() - subsequence.length() + 1; i++) {
for(j = 0; j < subsequence.length() &&
subsequence.charAt(j) == sequence.charAt(i + j); j++);
if(j == subsequence.length()) { // Matches
System.out.println("Match found at index " + i);
found++;
}
}
In this case, note that we must declare j
outside of the inner for
loop, since it will be used outside. This approach is more efficient
because we only need to perform the check once. Note that the
condition of the if
statement has also changed. Now, we know that all of
subsequence
matches because the loop ran to completion. If the loop
did not run to completion, then j
would be smaller than
subsequence.length()
and the loop must have terminated because the two
char
values did not match. Although more efficient, some programmers
would avoid this approach because it uses confusing syntax in which
the body of the for
loop is a single empty statement followed by a
semicolon. Likewise, the logic about exiting the loop and the condition
of the if
statement is murkier.
5.5. Concurrency: Loops
Many programmers use concurrency for speedup, to make their programs to run faster. Most programs that run for a long time use loops to do repetitive tasks. If these loops are doing the same operation to many different pieces of data, we may be able to speed up the process by splitting up the data and letting different threads operate on their own segment of the data. Splitting up data this way is called domain decomposition which allows us to achieve data parallelism. These topics are discussed further in Section 13.3.
Performing repetitive tasks is one of the great strengths of computers. For most programs that run a long time, incredible amounts of computation are being done inside of (usually nested) loops. Domain decomposition will not work for all of these programs. Some cannot be parallelized at all, but this book is about finding problems that can have parallel and concurrent solutions.
In Chapter 13, we’ll introduce tools for writing a concurrent program with different threads of execution running at the exactly the same time and potentially interacting. Using only the power of loops, you can see parallelism in action now.
Consider the problem of computing the sum of the sines of a range of integers. At its heart is a loop from the start of the range to the end.
for(int i = start; i <= end; i++)
sum += Math.sin(start);
If we want to allow the user to specify the start and the end and print out the sum, we need to make a program with a little bit of input and output around this loop.
import java.util.Scanner;
public class SumSines {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Enter starting value: ");
int start = in.nextInt();
System.out.print("Enter ending value: ");
int end = in.nextInt();
double sum = 0;
for(int i = start; i <= end; i++)
sum += Math.sin(start);
System.out.println("Sum of sines: " + sum);
}
}
If you compile and run this program with 1
as the start value and
100000000
as the end, the answer should be 1.7136493465700542
. One
hundred million values is a lot to find the sine for. Depending on your
machine, this task should take between 10 seconds and over a minute. Try
to time how long this takes as accurately as possible.
Now, open a total of four terminal windows and navigate them all to the
directory with SumSines.class
in it. Run SumSines
in each one. For
the first terminal, enter 1
as the start and 25000000
as the end. For
the second, enter 25000001
and 50000000
. For the third, enter
50000001
and 75000000
. For the last, enter 75000000
and
100000000
. Once they have run, you should get, respectively,
1.4912473269134603
, -0.6795491754132104
, -0.2893142602684644
, and
1.1912654553381272
. If you add these together using a calculator, you
should get 1.7136493465699127
, which is almost exactly the same answer
we got before. (Floating-point rounding errors cause the slight
difference.)
If you try to start them computing at about the same time, you can try to see how long it takes for all of them to complete. Did it take less time than before? If you have a single core processor, it might have taken just as long or longer. If you have a dual-core processor, it should have taken less time, and if you have a quad core processor, even less. Since we’re dividing the problem into four pieces, we don’t expect to see any improvement with more than four cores.
Most operating systems provide a graphical way of viewing the load on each processor. If you examine your CPU usage while running those programs, you should see it spike up when the programs start and then come down when they finish. For multiple cores, how did we say which core we wanted each program to run on? We didn’t. In general, it’s difficult to specify which core we want to run a program, process, or thread on. The OS does the job of scheduling and picks a free processor when it needs to run a program. It’s even possible for programs and threads to change from one core to another while running if the OS needs to balance out the workload.
This sines example is similar to Example 13.10 in Chapter 13. As you may have noticed, running four programs simultaneously is not convenient. You have to open several windows, you have to type starting and ending points very carefully, and you have to combine the answers at the end since your programs cannot interact directly with each other. Features of Java will make this job easier, allowing us to run more than one thread of execution at a time without the need to run multiple programs by hand.
5.6. Exercises
Conceptual Problems
-
If you have a
String
containing a long text and you want to count the number of words in the text that begin with the letter'm'
, which of the three kinds of loops would you use, and why? -
In Example 5.2, our last version of the primality tester
PrimalityTester2
computes the square root of the number being tested. Instead of computing this value before the loop, how would performance be affected by changing the head of thefor
loop to the following?for(long i = 3; i <= Math.sqrt(number) && prime; i += 2)
-
How many different DNA sequences of length n are there?
-
There are three different errors in the following loop intended to print out the numbers 1 through 10. What are they?
for(int i = 1; i < 10; i--); { System.out.println(i); }
-
Consider the following code containing nested
for
loops.Scanner in = new Scanner(System.in); int n = in.nextInt(); int count = 0; for(int i = 1; i <= n; i++) for(int j = 1; j <= i; j++) count++;
In terms of the value of
n
, how many times iscount
incremented? If it’s not immediately obvious, trace through the execution of the program by hand or run the code for several different values ofn
and try to detect a pattern.
Programming Practice
-
Write a program that converts base 10 numbers into base 3 numbers. If you find that task too easy, write a program that will convert base 10 numbers to any base in the range 2 to 16. Hint: Use letters A through Z, in order, to represent digits larger than 9.
-
The greatest common divisor (GCD) of two integers is the largest integer that divides both of them evenly. The GCD for any two positive integers is at least 1 and at most the smaller of the two numbers. Write a program that prompts a user for two
int
values and finds their GCD. Although there are more efficient methods, you can count down from either number. If the counter ever divides both numbers evenly, it’s the GCD. The counter is guaranteed to divide them both if it reaches 1. -
In the solution to the DNA searching problem given in Section 5.4, we used two
for
loops to find occurrences of a DNA subsequence inside of a larger sequence. Professional Java developers would have used a singlefor
loop and theindexOf()
method in theString
class. One version of this method returns the index of a substring within aString
object, starting from a particular offset, as shown below.String text = "fun dysfunction"; String search = "fun"; System.out.println("Location: " + text.indexOf(search, 4));
This code will output
Location: 7
since the first occurrence of"fun"
from index4
or later starts at index7
. If there are no more occurrences of the substring beyond the starting index, the method will return-1
. Rewrite the solution to the DNA searching problem, replacing the inner searchingfor
loop with theindexOf()
method. -
Write a program that reads a number n from a user and then prints all possible DNA sequences of length n. Be careful not to supply too large of a value when you run this program. Hint: Represent the sequence as a
String
. On each iteration, focus on the lastchar
in theString
. If it is an'A'
, change it to a'C'
. If it is a'C'
, change it to a'G'
. If it is a'G'
, change it to a'T'
. If it is a'T'
, change it back to an'A'
, but “carry” the increment over to the nextchar
, like a rolling odometer. You will have to design loops that can deal with carries that cascade across multiple indexes. -
Re-implement the solution to the DNA searching program given in Section 5.4 using
JOptionPane
to generate GUIs for input and output.
Experiments
-
Using a
for
loop, record the Monty Hall simulation so that you can run it 100 times, always choosing to switch doors. Keep a record of how many times you win. Change your code again to run the Monty Hall simulation 100 more times, always choosing to keep your initial choice. Again, keep a record of how many times you win. Compare the two records. Choosing to switch should perform roughly twice as well as sticking with your initial choice. Increase the number of iterations to 1,000 and then 10,000 times. Does the performance of switching get closer to twice the performance of not switching? -
Write three nested
for
loops, each of which run 1,000 times. Increment a counter in the innermostfor
loop. If that counter starts at 0, its final value should be 1,000,000,000. Time how long your program takes to run to completion using either a stopwatch or, if you’re on a Unix or Linux system, thetime
command. Feel free to increase and decrease the amount that each loop runs to see the effect on the time. However, if you increase the values of all three loops too much, you may have to wait a long while. -
In Section 5.3.5, one of the common loop mistakes we discuss is an almost infinite loop. Create your own almost infinite loop that runs from
10
to0
, incrementing instead of decrementing. Time the execution of your program. Unlike our example, do not use an output statement or your code will take too long to run. How much longer would your code take to run if you used along
instead of anint
? -
In Example 5.2, we gave three programs to test a number for primality. Run each of these prime testers on a large prime such as 982,451,653 and time them. Is there a significant difference in the running time of
PrimalityTester0
andPrimalityTester1
? What aboutPrimalityTester1
andPrimalityTester2
? -
In Example 5.5, we ran four programs at the same time to solve a problem in parallel. Use the same framework (combined with your knowledge of primes from Example 5.2) to write a program that can see how many prime numbers are in a user specified range of integers. Then, use it to find the total number of primes between 2 and 500,000,000. Now, run two copies of the program with one starting at 2 and going up to 250,000,000 and the other starting at 250,000,001 and going up to 500,000,000. If you add the numbers together, do you get the same answer? (If not, there is a bug in your program.) Now, divide the work into four pieces. How much quicker, if at all, is running all four programs instead of one? Does one of the four pieces run significantly faster or slower than the others?
6. Arrays
Too much of a good thing can be wonderful.
6.1. Introduction
With one exception, all of the types we’ve talked about in this book
have held a single value. For example, an int
variable can only
contain a single int
value. If you try to put a second int
value
into a variable, it will overwrite the first.
The String
type, of course, is the exception. String
objects can
contain char
sequences of any length from 0 up to a practically
limitless size (the theoretical maximum length of a Java String
is
Integer.MAX_INT
, more than 650 times the length of War and Peace).
As remarkable as String
objects are, this chapter is about a more
general kind of list called an array. We can create arrays to hold a
list of any type of variable in Java.
The ability to work with lists expands the scope of problems that we can solve. Beyond simple lists, we can use the same tools to create tables, grids, and other structures to solve fascinating problems like the one that comes next.
6.2. Problem: Game of Life
Some physicists insist that the rules governing the universe are horribly complicated.  With the power to do simulations quickly, computer scientists have shown that some systems can exhibit very complex interactions using simple rules. Perhaps the best known examples of these systems are cellular automata, of which Conway’s Game of Life is the most famous.
The framework for Conway’s Game of Life is an infinite grid made up of squares called cells.  Any given cell has 8 neighbors as shown in the figure below.
The pattern of alive and dead cells at any given time on the grid is called a generation. To determine the next generation, we use the following rules.
-
If a living cell has fewer than two living neighbors, it dies from loneliness.
-
If a living cell has more than three neighbors, it dies because of overcrowding.
-
If a living cell has exactly two or three living neighbors, it lives to the next generation.
-
If a dead cell has exactly three live neighbors, it becomes a living cell.
These four simple rules allow for more complex interactions than you might expect. The patterns that emerge from applying these rules to a starting configuration of alive and dead cells strike a balance between complete chaos and rigid order. As the name of the game implies, the similarity to biological patterns of development can be surprising.
Your problem is to create a Life simulator of size n × m, specific values for which will be discussed below. The program should simulate the process at a speed that is engaging to watch, with a new generation every tenth of a second. The program should begin by randomly making 10% of all the cells living and the rest dead.
6.2.1. Terminal limitations
One problem you might be worrying about is how to display the
simulation. In Chapter 15 you’ll learn how to make a graphical user interface (GUI)
that can display a grid of cells in black and white and much more
interesting things as well. For now, the main tool that we can use for
output is still the terminal. The output method we recommend is printing
an asterisk ('*'
) for a living cell and a space (' '
) for a dead
one. In this way you can easily see the patterns form on the screen and
change over time.
The classic terminal isn’t very big. For this reason, we suggest that you set the height of your simulation to 24 rows and the width of your simulation to 80 columns. These dimensions conform to the most ancient terminal sizes. If your terminal screen is much larger, you can change the width and height later to perform a larger simulation. No matter how large the display for the game is, the ideal size of the game. Because our size is so limited, we must deal with the problem of a cell on the boundary. Anything beyond the boundaries should be counted as dead. Thus, a cell right on the edge of the simulation grid can have a maximum of 5 neighbors. A cell in one of the four corners can only have 3 neighbors.
In order to give the appearance of smooth transitions, you need to print out each new generation of cells quickly, and in the same locations as the previous generation. Simply printing one set after another will not achieve this effect unless your terminal screen is exactly 24 rows tall. So, you will need to clear the screen each time. In an effort to be platform independent, Java does not provide an easy way to clear the terminal screen. A quick and simple hack is to simply print out 100 blank lines before printing the next generation. This hack will work as long as your terminal is not significantly more than 100 rows in height. If it is, you’ll need to print a larger number of blank rows.
Finally, you need to wait a short period of time between generations so that the user can see each configuration before it’s cleared away and replaced by the next one. The simplest way to do this is by having your program go to sleep for a short period of time, a tenth of a second as we suggested before. The code to make your program sleep for that amount of time is:
try { Thread.sleep(100); }
catch(InterruptedException e) {}
We’ll explain this code in much greater detail in Chapter 13.
The key item of importance is the number passed into the sleep()
method.
This value is the number of milliseconds you want your program to sleep.
100 milliseconds is, of course, one tenth of a second.
In order to simulate the Game of Life, we need to store information, namely the liveness or deadness of cells, in a grid. First, we need to discuss the simpler task of storing data in a list.
6.3. Concepts: Lists of data
Lists of data are of paramount importance in many different areas of life: shopping lists, packing lists, lists of employees working at a company, address books, top ten lists, and more. Lists are even more important in programming. As you know, one of the great strengths of computers is their speed. If we have a long list of data, we can use that speed to perform operations on all the data quickly. E-mail contact lists, entries in a database, and cells in a spreadsheet are just a few of the most obvious ways that lists come up in computer applications.
Even in Java, there are many different ways to record a list of information, but a list is only one form of data structure. As the name implies, a data structure is a way to organize data, whether in a list, in a tree, in sorted order, in some kind of hierarchy, or in any other way that might be useful. We’ll only talk about the array data structure in this chapter, but other data structures will be discussed in Chapter 18. Below, we give a short explanation of some of the attributes any given data structure might have.
6.3.1. Data structure attribute
- Contents
-
Keeping only a single value in a data structure defeats the purpose of a data structure. But, if we can store more than a single value, must all of those values come from the same type? If a data structure can hold several different types of data, we call it heterogeneous, but if it can only hold one type, we call it homogeneous.
- Size
-
The size of a data structure may be something that’s fixed when it’s created or it could change on the fly. If a data structure’s size or length can change, we call it a dynamic data structure. If the data structure has a size or length that can never change after it’s been created, we call it a static data structure.
- Element Access
-
One of the reasons there are so many different data structures is that different ways of structuring data are better or worse for a given task. For example, if your task is to add a list of numbers, then you’re expecting to access every single element in the list. However, if you’re searching for a word in a dictionary, you don’t want to check every dictionary entry to find it.
Some data structures are optimized so that you can efficiently read, insert, or delete only a single item, often the first (or last) item in the data structure. Some data structures only allow you to move through the structure sequentially, one item after another. Such a data structure has what is called sequential access. Still others allow you to jump randomly to any point you want inside the data structure efficiently. These data structures have what is called random access. Advanced programmers take into account many different factors before deciding which data structure is best suited to their problem.
6.3.2. Characteristics of an array
Now that we’ve defined these attributes, we can say that an array is a
homogeneous, static data structure with random access. An array is
homogeneous because it can only hold a list of a single type of data,
such as int
, double
, or String
. An array is static because it has
a fixed length that is set only when the array is instantiated. An array
also has random access because jumping to any element in the array is
fast and takes about the same amount of time as jumping to any
other.
An array is a list of a specific type of elements that has length n, a length specified when the array is created. Each of the n elements is indexed using a number between 0 and n - 1].  Consider the following list of items: {9, 4, 2, 1, 6, 8, 3}
If this list is stored in an array, the first element, 9, would have index 0, 4 would have index 1, and so on, finishing at 3 with an index of 6, although the total number of items is 7. Not all languages use zero-based counting for array indexes, but many do, including C, C++, and Java. The reason that languages like C originally used zero-based counting for indexes is that the variable corresponding to the array is an address inside the computer’s memory giving the first element in the array. Thus, an index of 0 is 0 times the size of an element added to the starting address, and an index of 5 is 5 times the size of an element added to the starting address. So, zero-based indexes gave a quick way for the program to compute where in memory a given element of an array is.
6.4. Syntax: Arrays in Java
The idea of a list is not mysterious. Numbering each element of the list is natural, even though the numbers start at 0 instead of 1. Nevertheless, arrays are the source of many errors that cause Java programs to crash. Below, we explain the basics of creating arrays, indexing into arrays, and using arrays with loops. Then, there’s an extra subsection explaining how to send data from a file to a program as if the file were being typed in by a user. Using this technique can save a lot of time when you’re experimenting with arrays.
6.4.1. Array declaration and instantiation
To create an array, you usually need to create an array variable first.
Remember that an array is a homogeneous data structure, meaning that it
can only store elements of a single type. When you create an array
variable, you have to specify what that type is. To declare an array
variable, you use the type it’s going to hold, followed by square
brackets ([]
), followed by the name of the variable. For example, if
you want to create an array called numbers
that can hold integers, you
would type the following.
int[] numbers;
If you have some C or C++ programming experience, you might be used to the brackets being on the other side of the variable, like so.
int numbers[];
In Java, both declarations are perfectly legal and equivalent. However,
the first declaration is preferred from a stylistic perspective. It
follows the pattern of using the type (an array of int
values in this
case) followed by the variable name as the syntax for a declaration.
As we said, arrays are also static data structures, meaning that their
length is fixed at the time of their creation. Yet we didn’t specify a
length above. This declaration has not yet created an array, just a
variable that can point at an array. In the second half of this chapter,
we will further discuss this difference between the way an array is
created and the way an int
or any other variable of primitive type is
created. To actually create the array, we need to use another step,
involving the keyword new
. Here’s how we instantiate an array of
int
type with 10 elements.
numbers = new int[10];
We use the keyword new
, followed by the type of element, followed by
the number of elements the array can hold in square brackets. This new
array is stored into numbers
. In other words, the variable numbers
is now a name for the array. Commonly, the two steps of declaring and
instantiating an array will be combined into one line of code.
int[] numbers = new int[10];