## Section6.6Conditional 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.

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:

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


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.

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

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