Java, Java, Java: Conditional Loops

9. Control Structures

9.6. Conditional Loops

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.

Sentinel bound

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.

The While Structure, Revisited

Consider the following pseudocode algorithm for the 3N+1 problem:

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

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.2:

Recall that unlike the for statement, the while statement does not con- tain syntax for the initializer and the updater. These must be coded sepa- rately. 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:

The while structure has the following form:

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 ini- tially? 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.

The while structure would be an appropriate control structure for the following type of problem:

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.

SELF-STUDY EXERCISES

EXERCISE 6.6Identify the syntax error in the following while struc- tures:

EXERCISE 6.7Determine the output and/or identify the error in each of the following while structures:

EXERCISE 6.8 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.

Problem description

Algorithm design

EXERCISE 6.9 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.

The 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 con- sidering 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 per-

cent, all the while counting the number of iterations required. Consider the following pseudocode algorithm:

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 Limit bound

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 appropri- ate for this problem, because we know in advance that the loop will iter- ate at least once. We can implement this algorithm using Java’s do-while statement:

The do-while statement is a loop statement in which the loop entry con- dition occurs after the loop body. It has the following general form:

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.

Figure 6.9: Flowchart of the do-while statement and do-while structure.

Do-While StatementDo-While Structure

To further highlight the difference between a loop statement and a loop structure, the do-while structure takes the following form:

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.9.

The do-while structure would be an appropriate control structure for the following type of problem:

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).

SELF-STUDY EXERCISES

EXERCISE 6.10Identify the syntax error in the following do-while

structures:

EXERCISE 6.11 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.

EXERCISE 6.12 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.

EXERCISE 6.13 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.