Section 6.3. Counting Loops
6.3. Counting LoopsA counting loop, or counter-controlled loop, is a loop in which you know beforehand how many times it will be repeated. Among the preceding examples, the first two are counting loops. Because you know the exact number of times the loop repeats beforehand, a counting loop can be made dependent on the value of a counter. For example, if you want to print the word "Hello" 100 times, you can use the following while structure: int k = 0; while (k < 100) { System.out.println("Hello"); k++; } In this case, the counter is the variable k, which counts from 0 through 99that is, it counts 100 times. Note that we start counting from 0 instead of 1. Counting from 0 is known as zero indexing, and it is a common programming convention for counting loops. Although it doesn't really make any practical difference in this case, later on we will use loops to process structures, such as strings and arrays, which use zero indexing. It will be easier to process these structures if our loop counter also starts at 0.
Zero indexing The variable k in this example is called a counter variable or loop counter. Although it is certainly possible to name the counter variable anything we like, it is customary to use single letters like i, j, and k as loop counters. The fundamental feature of a counting loop is that we must know beforehand exactly how many iterations the loop will take.
Loop counter Effective Design: Loop Design
Although we can use a while-structure to code a counting loop, Java's for statement is ideally suited for this purpose. For example, the following for statement will also print the word "Hello" 100 times: for (int k = 0; k < 100; k++) System.out.println("Hello"); In fact, this for statement is equivalent to the preceding while structure. The for statement has the following syntax: Java Language Rule: For Statement
The for statement begins with the keyword for, which is followed by a parenthesized list of three expressions separated by semicolons: an initializer, a loop-entry condition, and an updater. Following the parenthesized list is the for loop body, which is either a single statement or a sequence of statements contained in curly brackets, {. . .}. 6.3.1. The for StructureFigure 6.1 shows how the for statement works. It might be useful to compare this flowchart with the flowchart for the while structure (Fig. 6.2), which was introduced in Chapter 3. As you can see, it has exactly the same structure. The initializer is evaluated first. Thus, the initializer sets the integer variable k to 0. Then the loop-entry condition, which must be a boolean expression, is evaluated. If it is true, the body of the loop is executed; if it is false, the body of the loop is skipped and control passes to the next statement following the for statement. The updater is evaluated after the loop body is executed. After completion of the updater, the loop-entry condition is reevaluated and the loop body is either executed again or not, depending on the truth value of the loop-entry condition. This process is repeated until the loop-entry condition becomes false. Figure 6.1. Flowchart of the for statement. Figure 6.2. Flowchart of the while statement and while structure. Tracing the order in which the for loop components are evaluated gives this sequence: evaluate initializer evaluate loop entry condition ==> True execute for loop body; evaluate updater evaluate loop entry condition ==> True execute for loop body; evaluate updater evaluate loop entry condition ==> True execute for loop body; evaluate updater . . . evaluate loop entry condition ==> False As this trace shows, the loop-entry condition controls entry to the body of the loop and will, therefore, be the last thing done before the loop terminates. We have followed the standard convention of declaring the counter variable in the header of the for statement. This restricts the variable's scope to the for statement itself. It would be a syntax error to use k outside the scope of the for loop, as in this example: for (int k = 0; k < 100; k++) System.out.println("Hello"); // Syntax error, k undeclared System.out.println("k = " + k);
Loop variable scope For some problems, it might be necessary to use the loop variable outside the scope of the for statement, in which case the variable should be declared before the for statement. For example, if we want to print the value of the loop variable, k, after the loop completes, we have to declare it before the loop: int k = 0; // Declare the loop variable here for (k = 0; k < 100; k++) System.out.println("Hello"); System.out.println("k = " + k); // To use it here In this example, the loop will exit when k becomes 100, so "k = 100" will be printed. 6.3.2. Loop BoundsA counting loop starts at some initial value and counts zero or more iterations. A loop bound is a value that controls how many times a loop is repeated. A loop will repeat until its loop bound is reached. In a counting loop, the loop-entry condition should be a boolean expression that tests whether the loop's bound has been reached. Similarly, in a counting loop, the updater should modify the loop counter so that it makes progress toward reaching its bound. Counting loops often increment or decrement their counter by 1, depending on whether the loop is counting forward or backward. The following method contains a countdown loop, which prints 10 9 8 7 6 5 4 3 2 1 BLASTOFF. In this case, progress toward the loop bound is made by decrementing the loop counter: public void countdown() { for (int k = 10; k > 0; k--) System.out.print(k + " "); System.out.println("BLASTOFF"); } // countdown()
Loop bound Note in this case that we are using unit indexing instead of zero indexing, because countdowns repeat, or iterate, from 10 down to 1, not from 10 down to 0.
Unit indexing 6.3.3. Infinite LoopsIf the loop bound is never reached, the loop-entry condition will never become false and the loop will repeat forever. This is known as an infinite loop. Can you see why each of the following for statements will result in an infinite loop? for (int k = 0; k < 100; k--) // Infinite loop System.out.println("Hello"); for (int k = 1; k != 100; k+=2) // Infinite loop System.out.println("Hello"); for (int k = 98; k < 100; k = k / 2) // Infinite loop System.out.println("Hello");
Infinite loop In the first example, k starts out at 0 and is decremented on each iteration, taking on values -1,-2,-3, and so on, so k will never reach its loop bound. In the second example, k starts out at 1 and is incremented by 2 on each iteration, taking on the values 3, 5, 7, and so on. Because all these values are odd, k will never equal 100. A much safer loop bound in this case would be k <= 100. In the third example, k starts out at 98 and is halved on each iteration, taking on the values 49, 24, 12, 6, 3, 1, 0, 0, and so on, forever. Thus, it too will be stuck in an infinite loop. Encountering an unintended infinite loop when developing a program can be very frustrating. If the program is stuck in a loop that generates output, it will be obvious that it is looping, but if no output is being generated, the computer will appear to "freeze," no longer responding to your keyboard or mouse commands. Some programming environments allow you to break out of a looping program by typing a special keyboard command such as CONTROL-C or CTRL-ALT-DELETE or CONTROL-APPLE-ESCAPE, but if that doesn't work you will have to reboot the computer, possibly causing a loss of data. The best way to avoid infinite loops is to determine that the loop's updater expression will cause the loop to eventually reach its bound.
Stuck in a loop Effective Design: Loop Design
6.3.4. Loop IndentationNote how indentation is used to distinguish the loop body both from the heading and from the statement that follows the loop: for (int k = 10; k > 0; k--) // Loop heading System.out.print (k + " "); // Indent the body System.out.println( "BLASTOFF" ) // After the loop Indenting the loop body is a stylistic convention intended to make the code more readable. However, the indentation itself has no effect on how the code is interpreted by Java. Each of the following code segments would still produce the same countdown: for (int k = 10; k > 0; k--) System.out.print (k + " "); System.out.println("BLASTOFF"); for (int k = 10; k > 0; k--) System.out.print(k +" "); System.out.println("BLASTOFF"); for (int k = 10; k > 0; k--) System.out.print (k + " "); System.out.println("BLASTOFF"); In each case the statement, System.out.println("BLASTOFF"), is not part of the for loop body and is executed only once when the loop terminates. Java Programming Tip: Loop Indentation
Debugging Tip: Loop Indentation
Up to this point the loop body has consisted of a single statement, such as a println() statement. But the loop body may consist of any Java statement, including an if or if-else statement or a compound statement, which contains a sequence of statements enclosed within braces. Consider the following examples. The first example prints the sequence 0, 5, 10, 15, . . . 95. Its loop body consists of a single if statement: for (int k = 0; k < 100; k++) // Print 0 5 10... 95 if (k % 5 == 0) // Loop body: single if statement System.out.println("k= " + k); The next example prints the lowercase letters of the alphabet. In this case, the loop counter is of type char, and it counts the letters of the alphabet. The loop body consists of a single print() statement: for (char k = 'a'; k <= 'z'; k++) // Print 'a' 'b'... 'z' System.out.print (k + " "); // Loop body: single print() The next example prints the sequence 5, 10, 15, . . . 50, but it uses several statements within the loop body: for (int k = 1; k <= 10; k++) { // Print 5 10 15... 50 int m = k * 5; // Begin body System.out.print (m + " "); } // End body In this example, the scope of the local variable m, declared within the loop body, is limited to the loop body and cannot be used outside of that scope. Java Language Rule: Loop Body
Although braces are not required when the body of a for loop consists of a single statement, some coding styles recommend that braces should always be used for the body of a loop statement. For example, it is always correct to code a for loop as for (int k = 1; k <= 10; k++) { // Print 1 2 ... 10 System.out.print (k + " "); // Begin body } // End body Another advantage of this coding style is that you can easily place additional statements in the loop body by placing them within the braces. Debugging Tip: Missing Braces
Self-Study Exercises
6.3.5. Nested LoopsA nested loop is a structure in which one loop is contained inside the body of another loop, as when a for loop body contains a for loop. For example, suppose you are working for Giant Auto Industries, and your boss wants you to print a table for buyers to figure the cost of buying multiple quantities of a certain part. The cost of individual parts ranges from $1 to $9. The cost of N items is simply the unit price times the quantity. Thus, you'll want to print something like the following table of numbers, where the prices per unit are listed in the top row, and the prices for two, three, and four units are listed in subsequent rows: 1 2 3 4 5 6 7 8 9 2 4 6 8 10 12 14 16 18 3 6 9 12 15 18 21 24 27 4 8 12 16 20 24 28 32 36 To produce this multiplication table, we could use the following nested for loops: 1. for (int row = 1; row <= 4 ; row++) { // For each of 4 rows 2. for (int col = 1; col <= 9; col++) // For each of 9 columns 3. System.out.print(col * row + "\t" ); // Print number 4. System.out.println(); // Start a new row 5. } // for row Note how indenting is used here to distinguish the levels of nesting and to make the code more readable. In this example, the outer loop controls the number of rows in the table, hence our choice of row as its loop counter. The println() statement is executed after the inner loop is done iterating, which allows us to print a new row on each iteration of the outer loop. The inner loop prints the nine values in each row by printing the expression col * row. Obviously, the value of this expression depends on both loop variables.
Inner and outer loop Let's dissect this example a bit. How many times is the for statement in line 2 executed? The inner loop is executed once for each iteration of the outer loop. Thus, it is executed four times, which is the same number of times that line 4 is executed. How many times is the statement on line 3 executed? The body of the inner loop is executed 36 timesnine times for each execution of line 2. Sometimes it is useful to use the loop variable of the outer loop as the bound for the inner loop. For example, consider the following pattern: # # # # # # # # # # # # # # #
Algorithm design The number of # symbols in each row varies inversely with the row number. In row 1, we have five symbols; in row 2 we have four; and so on down to row 5, where we have one #. To produce this kind of two-dimensional pattern, we need two counters: one to count the row number, and one to count the number of # symbols in each row. Because we have to print each row's symbols before moving on to the next row, the outer loop will count row numbers, and the inner loop will count the symbols in each row. But note that the inner loop's bound will depend on the row number. Thus, in row 1 we want five symbols; in row 2 we want four symbols; and so on. If we let row be the row number, then in each row we want to print 6- row symbols. The following table shows the relationship we want:
If we let j be the counter for the inner loop, then j will be bound by the expression 6row. This leads to the following nested loop structure: for (int row = 1; row <= 5; row++) { // For each row for (int j = 1; j <= 6 - row; j++) // Print the row System.out.print('#'); System.out.println(); // Start a new line } // for row Note that the bound of the inner loop varies according to the value of row, the loop counter for the outer loop. Self-Study Exercise
|
EAN: 2147483647
Pages: 275