Unlike the problems in the previous sections, not all loops can be coded as counting loops. Here’s a problem that can’t be solved by a counting loop.
Mathematicians, especially number theorists, have found that certain operations on numbers lead to interesting sequences. For example, the 3N+1 problem is a conjecture in number theory, which says that if N is any positive integer, then the sequence generated by the following rules will always terminate at 1.
Case Operation
---- ---------
N is odd N = 3 * N + 1
N is even N = N / 2
In other words, start with any positive integer, N. If N is odd, multiply it by 3 and add 1. If N is even, divide it by 2. In either case, assign the result back to N. The conjecture states that N will eventually equal 1. For example, if N is initially 26, then the sequence generated is 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.
The 3N+1 problem is an example of a noncounting loop. Because for any given N we don’t know how long the 3N+1 sequence will be, we need a loop that terminates when the loop variable reaches a certain value, called a sentinel value—when N equals 1. This is an example of a loop that is terminated by a sentinel bound. With the exception of infinite loops, all loops are bounded by some condition, which is why they are sometimes referred to as conditional loop structures. The count and sentinel bounds are just special cases of the conditional loop structure.
Subsection6.6.1The While Structure, Revisited
Consider the following pseudocode algorithm for the 3N+1 problem:
Algorithm for computing the 3N+1 sequence
While N is not equal to 1, do: {
Print N.
If N is even, divide it by 2.
If N is odd, multiply N by 3 and add 1.
}
Print N
In this structure, the body of the loop prints N and then updates N’s value, using the 3N+1 rules. Suppose N equals 5 when this code segment begins. It will print the following sequence: 5, 16, 8, 4, 2, 1. Note that the loop body is entered as long as N is not equal to 1. So the loop entry condition in this case is N != 1. Conversely, the loop will terminate when N equals 1. Also note that in this code segment the loop bound is tested before the body of the loop is executed.
We can implement this algorithm using Java’s while statement, whose flowchart is shown in Figure 6.3.4:
while (N != 1) { // While N not equal to 1
System.out.print(N + " ");// Print N
if (N % 2 == 0) // If N is even
N = N / 2; // divide it by 2
else // If N is odd
N = 3 * N + 1; // multiply by 3 and add 1
}
System.out.println(N); // Print N
Recall that unlike the for statement, the while statement does not contain syntax for the initializer and the updater. These must be coded separately. As we pointed out in Chapter 3, the while structure (as opposed to the while statement) is a segment of code built by the programmer that satisfies the following design principle:
Principle6.6.1.EFFECTIVE DESIGN: Loop Structure.
A properly designed loop structure must include an initializer, a loop-entry condition, and an updater. The updater should guarantee that the loop-entry condition will eventually become false, thereby causing the loop to terminate.
The while structure has the following form:
InitializerStatements; // Initializer
while (loop entry condition) { // Bound test
Statements; // Loop body
UpdaterStatements; // Updater
}
As its form suggests, the while structure is designed so that on some conditions the loop body will never be executed. Because it tests for the loop bound before the loop body, it is possible that the loop body is never executed. We might say that it is designed to perform 0 or more iterations.
For example, going back to the 3N+1 problem, what if N equals 1 initially? In that case, the loop body will be skipped, because the loop entry condition is false to begin with. No iterations will be performed, and the algorithm will simply print the value 1.
Here’s a simpler problem. Assume you’re working your way through a set of problems in an assignment. You could follow the pseudocode below and use a while loop.
write the problems on the assignment sheet // Initializer
while there are problems on the sheet // Bound test
do a problem // Loop body
cross it off the assignment sheet // Updater
It is possible that the assignment sheet contains no homework problems to begin with. In that case, there’s no work for the body of the loop to do and it should be skipped.
ExercisesSelf-Study Exercises
Identify and fix the syntax error in the following while loop structures.
1.While Loop Bugs 1.
Fix the bugs in the following while loop.
2.While Loop Bugs 2.
Fix the bugs in the following while loop.
3.While Loop Bugs 3.
Fix the bugs in the following while loop.
4.While Loop Bugs 4.
Fix the bugs in the following while loop.
5.Count by 6’s.
Your younger sister is now learning how to count by sixes. Write a while loop that prints the following sequence of numbers: 0, 6, 12, 18, 24, 30, 36.
6.While Sequence.
Here’s another number theory problem. Start with any positive integer, N. If N is even, divide it by 2. If N is odd, subtract 1 and then divide it by 2. This will generate a sequence that is guaranteed to terminate at 0. For example, if N is initially 15, then you get the sequence: 15, 7, 3, 1, 0. Write a method that implements this sequence using a while statement.
Subsection6.6.2The Do-While Structure
Here’s another problem that can’t be solved with a counting loop. Your father has been fretting about the bare spots on the front lawn and is considering hiring the ChemSure Lawn Service to fertilize. However, your scientifically minded younger sister wants to reassure him that at the rate the grass is dying, there will be enough to last through the summer. Using techniques she learned in biology, your sister estimates that the grass is dying at the rate of 2 percent per day. How many weeks will it take for half the lawn to disappear?
One way to solve this problem would be to keep subtracting 2 percent from the current amount of grass until the amount dipped below 50 percent, all the while counting the number of iterations required. Consider the following pseudocode algorithm:
Algorithm for calculating grass loss
Initialize amtGrass to 100.0
Initialize nDays to 0
Repeat the following statements
amtGrass -= amtGrass * 0.02;
++nDays;
As long as amtGrass > 50.0
Print nDays / 7
We begin by initializing amtGrass to 100.0, representing 100 percent. And we initialize our counter, nDays to 0. Then we repeatedly subtract 2 percent of the amount and increment the counter until the amount drops below 50 percent. In other words, in this case, we repeat the loop body as long as the amount of grass remains above 50 percent of the original. When the loop finishes, we report the number of weeks it took by dividing the number of days by 7.
The loop bound in this case is known as a limit bound. The loop will terminate when a certain limit has been reached—in this case, when the amount of grass dips below 50 percent of the original amount. Note that in this case the loop bound is tested after the loop body. This is appropriate for this problem, because we know in advance that the loop will iterate at least once. We can implement this algorithm using Java’s do-while statement:
public int losingGrass(double perCentGrass) {
double amtGrass = 100.0; // Initialize amount grass
int nDays = 0; // Initialize day counter
do { // Repeat
amtGrass -= amtGrass * LOSSRATE; // Update amount
++nDays; // Increment the counter
} while (amtGrass > perCentGrass);
// As long as enough grass remains
return nDays / 7; // Return the number of weeks
} // losingGrass()
Principle6.6.2.Do-while Statement.
The do-while statement is a loop statement in which the loop entry condition occurs after the loop body. It has the following syntax:
do {
loop body
} while(loop condition);
Note, again, that unlike the for statement, the do-while statement does not contain syntax for the initializer and the updater. These must be coded separately.
To further highlight the difference between a loop statement and a loop structure, the do-while structure takes the following form:
InitializerStatements1; // Initializer
do { // Beginning of loop body
InitializerStatements2; // Another initializer
Statements; // Loop body
UpdaterStatements // Updater
} while (loop entry condition); // Bound test
Note that initializer statements may be placed before the loop body, at the beginning of the loop body, or in both places, depending on the particular problem. Like the other loop structures, updater statements occur within the body of the loop. A flowchart of the do-while structure is shown in Figure 6.6.3.
Figure6.6.3.Flowchart of the do-while statement and do-while structure.
The do-while structure would be an appropriate control structure for the following type of problem:
do
dial the desired telephone number // Initializer
if you get a busy signal
hang up // Updater
while there is a busy signal // Bound test
In this case, you want to perform the actions in the body of the loop at least once and possibly more than once (if you continue to receive a busy signal).
Principle6.6.4.EFFECTIVE DESIGN: Do-While Loops.
The do-while loop is designed for solving problems in which at least one iteration must occur.
Principle6.6.5.EFFECTIVE DESIGN: While versus Do-While Structures.
For problems where a noncounting loop is required, the while loop structure is more general and, therefore, preferable to the do-while structure. Use do-while only when at least one iteration must occur.
ExercisesSelf-Study Exercises
Identify and fix the syntax error in the following do-while loop structures.
1.Do While Loop Bugs 1.
Fix the bugs in the following do-while loop.
2.Do While Loop Bugs 2.
Fix the bugs in the following do-while loop.
3.Count by 7’s.
Your sister has moved on to counting by sevens. Write a do-while loop that prints the following sequence of numbers: 1, 8, 15, 22, 29, 36, 43.
4.Pizza Costs.
Do the following coding assignment using a Java development environment that allows user input. As the owner of Pizza Heaven, every night at the close of business you quickly enter the price of every pizza ordered that day. You take the data from the servers’ receipts. Pizzas cost $8, $10, or (the Heavenly Special) $15. You enter the data without dollar signs, and use 99 to indicate you’re finished for the day. Write a Java method to input and validate a single pizza data item. If an incorrect price is entered, the program should print an error message and prompt for corrected input. Correct input is used to compute a daily total.
5.Pizza Codes.
Do the following coding assignment using a Java development environment that allows user input. Because the pizza prices in the previous exercise are fixed, change the method so you can save time on keyboarding. Instead of entering the price, you’ll enter codes of 1, 2, or 3 (corresponding to the $8, $10, and $15 pizzas), and 0 to indicate that you’re finished. Validate that the data value entered is correct and then convert it to the corresponding price before returning it.
