Section 6.6. Conditional Loops
6.6. Conditional LoopsUnlike the problems in the preceding sections, not all loops can be coded as counting loops. Here is 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 we don't know how long the 3N+1 sequence will be for any given N, we need a loop that terminates when the loop variable reaches a certain value, called a sentinel valuewhen 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.
Sentinel bound 6.6.1. The while Structure RevisitedConsider 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.2: 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: Effective Design: Loop Structure
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, the loop body may never be executed. We might say that the while structure is designed to perform zero 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. Self-Study Exercises
6.6.2. The do-while StructureHere'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?
Problem description One way to solve this problem would be to keep subtracting 2 percent from the current amount of grass until the amount dips 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
Algorithm design 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 reachedin 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()
Limit bound 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: Java Language Rule Do-While Statement
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 Initializer statements may be placed before the loop body, at the beginning of the loop body, or in both places, depending on the 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. Figure 6.9. 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). Effective Design: Do-While Loop
Effective Design: While versus Do-While Structures
Self-Study Exercises
|
EAN: 2147483647
Pages: 275