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

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.

The 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 [fig-whileflow6]:

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.

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

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.

Identify the syntax error in the following while structures:

int k = 5;
while (k < 100) {
    System.out.println(k);
    k++
}

int k = 0;
while (k < 12 ;) {
   System.out.println(k);
   k++;
}

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

int k = 0;
while (k < 100)
    System.out.println(k);

while (k < 100) {
    System.out.println(k);
    k++;
}

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.

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

The do-while statement is a loop statement in which the loop entry condition 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.

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 [fig-dowhileflow].

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

Identify the syntax error in the following do-while

int k = 0;
do while (k < 100)
{    System.out.println(k);
     k++
}

int k = 0;
do {
    System.out.println(k);
    k++;
} while (k < 12)

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.

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.

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.