In Chapter 5, we said that the flow of control in a program can differ from the physical order of the statements. The physical order is the order in which the statements appear in a program; the order in which we want the statements to be executed is called the logical order.

The If statement is one way of making the logical order differ from the physical order. Looping control structures are another. A loop executes the same statement (simple or compound) over and over, as long as a condition or set of conditions is satisfied.

In this chapter, we discuss different kinds of loops and explore how they are constructed using the While statement. We also discuss nested loops (loops that contain other loops) and introduce a notation for comparing the amount of work done by different algorithms.

6.1 The While Statement

The While statement, like the If statement, tests a condition. Here is the syntax template for the While statement:

Here is an example of one:

while (inputVal != 25)
  cin >> inputVal;

The While statement is a looping control structure. The statement to be executed each time through the loop is called the body of the loop. In the preceding example, the body of the loop is the input statement that reads in a value for inputVal. This While statement says to execute the body repeatedly as long as the input value does not equal 25. The While statement is completed (hence, the loop stops) when inputVal equals 25. The effect of this loop, then, is to consume and ignore all the values in the input stream until the number 25 is read.

Figure 6.1 While Statement Flow of Control

Just like the condition in an If statement, the condition in a While statement can be an expression of any simple data type. Nearly always, it is a logical (Boolean) expression; if not, its value is implicitly coerced to type bool (recall that a zero value is coerced to false, and any nonzero value is coerced to true). The While statement says, “If the value of the expression is true, execute the body and then go back and test the expression again. If the expression's value is false, skip the body.” The loop body is thus executed over and over as long as the expression is true when it is tested. When the expression is false, the program skips the body and execution continues at the statement immediately following the loop. Of course, if the expression is false initially, the body is never executed. FIGURE 6.1 shows the flow of control of the While statement, where Statement1 is the body of the loop and Statement2 is the statement following the loop.

The body of a loop can be a compound statement (block), which allows us to execute any group of statements repeatedly. Most often we use While loops in the following form:

while (Expression)
{
   .
   .
   .
}

In this structure, if the expression is true, the entire sequence of statements in the block is executed, and then the expression is checked again. If it is still true, the statements are executed again. The cycle continues until the expression becomes false.

Although in some ways the If and While statements are alike, some fundamental differences distinguish them (see FIGURE 6.2). In the If structure, Statement1 is either skipped or executed exactly once. In the While structure, Statement1 can be skipped, executed once, or executed over and over. The If is used to choose a course of action; the While is used to repeat a course of action.

Figure 6.2 A Comparison of If and While

6.2 Phases of Loop Execution

The body of a loop is executed in several phases:

The moment that the flow of control reaches the first statement inside the loop body is the loop entry.

Each time the body of a loop is executed, a pass is made through the loop. This pass is called an iteration.

Before each iteration, control is transferred to the loop test at the beginning of the loop.

When the last iteration is complete and the flow of control has passed to the first statement following the loop, the program has exited the loop. The condition that causes a loop to be exited is the termination condition. In the case of a While loop, the termination condition is that the While expression becomes false.

Notice that the loop exit occurs at only one point: when the loop test is performed. Even though the termination condition may become satisfied midway through the execution of the loop, the current iteration is completed before the computer checks the While expression again.

The concept of looping is fundamental to programming. In this chapter, we spend some time looking at typical kinds of loops and ways of implementing them with the While statement. These looping situations come up again and again when you are analyzing problems and designing algorithms.

6.3 Loops Using the While Statement

In solving problems, you will come across two major types of loops: count-controlled loops, which repeat a specified number of times, and event-controlled loops, which repeat until something happens within the loop.

If you are making an angel food cake and the recipe reads, “Beat the mixture 300 strokes,” you are executing a count-controlled loop. If you are making a pie crust and the recipe reads, “Cut with a pastry blender until the mixture resembles coarse meal,” you are executing an event-controlled loop; you don't know ahead of time the exact number of loop iterations.

Count-Controlled Loops

A count-controlled loop uses a variable we call the loop control variable in the loop test. Before we enter a count-controlled loop, we have to initialize (set the initial value of) the loop control variable and then test it. Then, as part of each iteration of the loop, we must increment (increase by 1) the loop control variable. Here's an example in a program that repeatedly outputs “Hello!” on the screen:

In the Hello program, loopCount is the loop control variable. It is set to 1 before loop entry. The While statement tests the expression

loopCount <= 10

and executes the loop body as long as the expression is true. Inside the loop body, the main action we want to be repeated is the output statement. The last statement in the loop body increments loopCount by adding 1 to it.

Notice the form of the statement in which we increment the loop control variable:

variable = variable + 1;

This statement adds 1 to the current value of the variable, and the result replaces the old value. Variables that are used this way are called counters. In the Hello program, loopCount is incremented with each iteration of the loop—we use it to count the iterations. The loop control variable of a count-controlled loop is always a counter.

Of course, we've encountered another way of incrementing a variable in C++. The incrementation operator (++) increments the variable that is its operand. The statement

loopCount++;

has precisely the same effect as the assignment statement

loopCount = loopCount + 1;

From here on, we typically use the ++ operator, as do most C++ programmers.

When designing loops, it is the programmer's responsibility to see that the condition to be tested is set correctly (initialized) before the While statement begins. The programmer also must make sure that the condition changes within the loop so that it eventually becomes false; otherwise, the loop is never exited.

A loop that never exits is called an infinite loop because, in theory, the loop executes forever. In the preceding code, omitting the incrementation of loopCount at the bottom of the loop leads to an infinite loop; the While expression is always true because the value of loopCount is forever 1. If your program goes on running for much longer than you expected, chances are that you've created an infinite loop. You may have to issue an operating system command to stop the program.

How many times does the loop in our Hello program execute—9 or 10? To answer this question, we have to look at the initial value of the loop control variable and then at the test to see what its final value is. Here we've initialized loopCount to 1, and the test indicates that the loop body is executed for each value of loopCount up through 10. If loopCount starts out at 1 and runs up to 10, the loop body is executed 10 times. If we want the loop to execute 11 times, we have to either initialize loopCount to 0 or change the test to

loopCount <= 11

Remember the program we developed in Chapter 2 that prints a checkerboard? Here is the algorithm:
 

 Repeat four times
  Output five whiteRows
  Output five blackRows

Because we didn't know how to write loops then, we had to repeat the code four times. Here is the revised program with the code written using a loop:

Event-Controlled Loops

Several kinds of event-controlled loops exist: sentinel controlled, end-of-file controlled, and flag controlled. In all of these loops, the termination condition depends on some event occurring while the loop body is executing.

Sentinel-Controlled Loops

Loops are often used to read in and process long lists of data. Each time the loop body is executed, a new piece of data is read and processed. Often a special data value, called a sentinel or trailer value, is used to signal the program that no more data remains to be processed. Looping continues as long as the data value read is not the sentinel; the loop stops when the program recognizes the sentinel. In other words, reading the sentinel value is the event that controls the looping process.

A sentinel value must be something that never shows up in the normal input to a program. For example, if a program reads calendar dates, we could use February 31 as a sentinel value:

There is a problem in the loop in this example. The values of month and day are not defined before the first pass through the loop. Somehow we have to initialize these variables. We could assign them arbitrary values, but then we would run the risk that the first values input are the sentinel values, which would then be processed as data. Also, it's inefficient to initialize variables with values that are never used.

We can solve this problem by reading the first set of data values before entering the loop. This practice is called a priming read. (The idea is similar to priming a pump by pouring a bucket of water into the mechanism before starting it.) Let's add the priming read to the loop:

With the priming read, if the first values input are the sentinel values, then the loop correctly does not process them. We've solved one problem, but now there is a problem when the first values input are valid data. The first thing the program does inside the loop is to get a date, thereby destroying the values obtained by the priming read. Thus the first date in the data list is never processed. Given the priming read, the first thing that the loop body should do is process the data that's already been read. But at what point do we then read the next data set? We do this last in the loop. In this way, the While condition is applied to the next data set before it gets processed. Here's how it looks:

This segment works correctly. The first data set is read in; if it is not the sentinel, it gets processed. At the end of the loop, the next data set is read in, and we go back to the beginning of the loop. If the new data set is not the sentinel, it gets processed just like the first. When the sentinel value is read, the While expression becomes false and the loop exits (without processing the sentinel).

Often the problem dictates the value of the sentinel. For example, if the problem does not allow data values of 0, then the sentinel value should be 0. Sometimes a combination of values is invalid. The combination of February and 31 as a date is such a case. Sometimes a range of values (negative numbers, for example) is the sentinel.

When you process char data one line of input at a time, the newline character (' ') often serves as the sentinel. Here's a program that reads and prints all of the characters from one line of an input file:

Notice that for this particular task we use the get function, not the >> operator, to input a character. Recall that the >> operator skips whitespace characters—including blanks and newlines—to find the next data value in the input stream. In this program, we want to input every character, even a blank and especially the newline character.

What if there aren't any invalid data values that you can use as a sentinel? Then you may have to input an extra value in each iteration, a value whose only purpose is to signal the end of the data. For example, the second value on each line of the following data set is used to indicate whether more data is present. When the sentinel value is 0, there is no more data; when it is 1, there is more data.

It's extremely rare to encounter a problem that needs to be solved with this technique. Most programs input multiple data values in each iteration. As a program's input becomes more complex, the more likely it is that some combination of values will be invalid. (That also implies we need to be more careful to check that the input is correct!)

What happens if you forget to enter the sentinel value? In an interactive program, the loop executes again, prompting for input. At that point, you can enter the sentinel value. If the input to the program comes from a file, once all the data has been read, the loop body is executed again. However, there isn't any data left—because the computer has reached the end of the file—so the file stream enters the fail state. In the next section, we describe a way to use the end-of-file situation as an alternative to using a sentinel.

Before we move on, we should mention an issue that is related not to the design of loops but rather to C++ language usage. In Chapter 5, we talked about the common mistake of using the assignment operator (=) instead of the relational operator (==) in an If condition. This same mistake can happen when you write While statements. See what happens when we use the wrong operator in the previous example:

This mistake creates an infinite loop. The While expression is now an assignment expression, not a relational expression. The expression's value is 1 (interpreted in the loop test as true because it's nonzero), and its side effect is to store the value 1 into sentinel, replacing the value that was just input into the variable. Because the While expression is always true, the loop never stops.

End-of-File-Controlled Loops

You have already learned that an input stream (such as cin or an input file stream) goes into the fail state (1) if it encounters unacceptable input data, (2) if the program tries to open a nonexistent input file, or (3) if the program tries to read past the end of an input file. Let's look at the third of these three possibilities.

After a program has read the last piece of data from an input file, the computer is at the end of the file (EOF, for short). At this moment, the stream state is in a successful state. But if we try to input even one more data value, the stream goes into the fail state. We can use this fact to our advantage: To write a loop that inputs an unknown number of data items, we can use the failure of the input stream as a form of sentinel.

In Chapter 5, we described how to test the state of an I/O stream. In a logical expression, we use the name of the stream as though it were a Boolean variable:

In such a test, the result is true if the most recent I/O operation succeeded, or false if it failed. In a While statement, testing the state of a stream works in the same way. Suppose we have a data file containing integer values. If inData is the name of the file stream in our program, here's a loop that reads and echoes all of the data values in the file:

inData >> intVal;          // Get first value
while (inData)             // While the input succeeded…
{
  cout << intVal << endl;  // Echo it
  inData >> intVal;        // Get next value
}

Let's trace this code, assuming the file contains three values: 10, 20, and 30. The priming read inputs the value 10. The While condition is true because the input succeeded, and the computer executes the loop body. First the body prints out the value 10, and then it inputs the second data value, 20. Looping back to the loop test, the expression inData is true because the input succeeded. The body executes again, printing the value 20 and reading the value 30 from the file. Looping back to the test, the expression is true. Even though we are at the end of the file, the stream state is still okay—the previous input operation succeeded. The body executes a third time, printing the value 30 and executing the input statement. This time, the input statement fails, because we're trying to read beyond the end of the file. The stream inData enters the fail state. Looping back to the loop test, the value of the expression is false and we exit the loop.

When we write EOF-controlled loops like the previous example, we expect that the end of the file will be the reason for stream failure. But keep in mind that any input error causes stream failure. The preceding loop terminates, for example, if input fails because of invalid characters in the input data. This fact emphasizes again the importance of echo printing. It helps us verify that all the data was read correctly before the EOF was encountered.

EOF-controlled loops are similar to sentinel-controlled loops in that the program doesn't know in advance how many data items will be input. In the case of sentinel-controlled loops, the program reads data until it encounters the sentinel value. With EOF-controlled loops, it reads data until it reaches the end of the file.

The following program uses an EOF-controlled loop to read and print the int values from a file.

Here is its output from a sample run:

Flag-Controlled Loops

A flag is a Boolean variable that is used to control the logical flow of a program. We can set a Boolean variable to true before a While loop; then, when we want to stop executing the loop, we can reset it to false. That is, we can use the Boolean variable to record whether the event that controls the process has occurred. For example, the following code segment reads and sums values until the input value is negative. (nonNegative is the Boolean flag; all of the other variables are of type int.)

sum = 0;
nonNegative = true;         // Initialize flag
while (nonNegative)
{
  cin >> number;
  if (number < 0)           // Test input value
    nonNegative = false;    // Set flag if event occurred
  else
    sum = sum + number;
}

Notice that we can code sentinel-controlled loops with flags. In fact, this code uses a negative value as a sentinel.

You do not have to initialize flags to true; you can initialize them to false. If you do, you must use the NOT operator (!) in the While expression and reset the flag to true when the event occurs. The following program, which calculates the square root of an input value, uses this approach. An initial value for the square root (guess) is calculated, goodEnough is set to false, and the loop continues recalculating guess until the absolute value of guess*guess is within 0.001 of the original value. Function fabs in <cmath> calculates the absolute value.

Here is the output from a sample run:

Looping Subtasks

We have been looking at ways to use loops to affect the flow of control in programs. In fact, looping by itself does nothing. The loop body must perform a task for the loop to accomplish something. In this section, we look at three tasks—counting, summing, and keeping track of a previous value—that often are performed in loops.

Counting

A common task in a loop is to keep track of the number of times the loop has been executed. For example, the following program fragment reads and counts input characters until it comes to a period. (inChar is of type char; count is of type int.) The loop in this example has a counter variable, but the loop is not a count-controlled loop because the variable is not being used as a loop control variable.

count = 0;                 // Initialize counter
cin.get(inChar);           // Read the first character
while (inChar != '.')
{
  count++;                 // Increment counter
  cin.get(inChar);         // Get the next character
}

The loop continues until a period is read. After the loop is finished, count contains one less than the number of characters read. That is, it counts the number of characters up to, but not including, the sentinel value (the period). Notice that if a period is the first character, the loop body is not entered and count contains 0, as it should. We use a priming read here because the loop is sentinel controlled.

The counter variable in this example is called an iteration counter because its value equals the number of iterations through the loop.

According to our definition, the loop control variable of a count-controlled loop is an iteration counter. However, as you've just seen, not all iteration counters are loop control variables.

Summing

Another common looping task is to sum a set of data values. Notice in the following example that the summing operation is written the same way, regardless of how the loop is controlled.

sum = 0;                   // Initialize the sum
count = 1;
while (count <= 10)
{
  cin >> number;           // Input a value
  sum = sum + number;      // Add the value to sum
  count++;
}

We initialize sum to 0 before the loop starts so that the first time the loop body executes, the statement

sum = sum + number;

adds the current value of sum (0) to number to produce the new value of sum. After the entire code fragment has executed, sum contains the total of the ten values read, count contains 11, and number contains the last value read.

In the preceding example, count is being incremented in each iteration. For each new value of count, there is a new value for number. Does this mean we could decrement count by 1 and inspect the previous value of number? No. Once a new value has been read into number, the previous value is gone forever—that is, unless we've saved it in another variable. We'll see how to do so in the next section.

Let's look at another example. We want to count and sum the first ten odd numbers in a data set. We need to test each number to see if it is even or odd. (We can use the modulus operator to find out: If number % 2 equals 1, number is odd; otherwise, it's even.) If the input value is even, we do nothing. If it is odd, we increment the counter and add the value to our sum. We use a flag to control the loop because this is not a normal count-controlled loop. Here is a listing of the application and the output.

Sample output:

In this example, there is no relationship between the value of the counter variable and the number of times the loop is executed. We could have written the While expression this way:

while (count < 10)

but this might mislead a reader into thinking that the loop is count controlled in the normal way. Instead, we control the loop with the flag lessThanTen to emphasize that count is incremented only when an odd number is read. The counter in this example is an event counter; it is initialized to 0 and incremented only when a certain event occurs. The counter in the previous example was an iteration counter; it was initialized to 1 and incremented during each iteration of the loop.

Before we leave this example, we need to point out a shortcut we used in the code. Look at the following two statements:

int count = 0;  // Initialize event counter
int sum = 0;    // Initialize sum

We declared these two variables and initialized them in the same statement. This practice is quite legal. In fact, we used this shortcut once before in an earlier program. Did you notice it? In Chapter 9, we look at this construct a little more closely.

Keeping Track of a Previous Value

Sometimes we want to remember the previous value of a variable. Suppose we want to write a program that counts the number of not-equal operators (!=) in a file that contains a C++ program. We can do so by simply counting the number of times an exclamation mark (!) followed by an equal sign (=) appears in the input. One way in which to accomplish this task is to read the input file one character at a time, keeping track of the two most recent characters—that is, the current value and the previous value. In each iteration of the loop, a new current value is read and the old current value becomes the previous value. When EOF is reached, the loop is finished. Here's a program that counts not-equal operators in this way:

File myfile.dat:

<= !!! === != ! = !=

Output:

Study this loop carefully, because it's going to come in handy. There are many problems in which you must keep track of the last value read in addition to the current value.

6.4 How to Design Loops

It's one thing to understand how a loop works when you look at it, and something else again to design a loop that solves a given problem. In this section, we consider the process of designing loops. We can divide this process into two tasks: designing the control flow and designing the processing that takes place in the loop. We can, in turn, break each task into three phases: the task itself, initialization, and update. It's also important to specify the state of the program when it exits the loop, because a loop that leaves variables and files in a mess is not well designed.

There are seven points to consider in designing a loop:

1. What is the condition that ends the loop?

2. How should the condition be initialized?

3. How should the condition be updated?

4. What is the process being repeated?

5. How should the process be initialized?

6. How should the process be updated?

7. What is the state of the program on exiting the loop?

We will use these questions as a checklist. The first three help us design the parts of the loop that control its execution. The next three help us design the processing within the loop. The last question reminds us to make sure that the loop exits in an appropriate manner.

Designing the Flow of Control

The most important step in loop design is deciding what should make the loop stop. If the termination condition isn't well thought out, our program might potentially contain infinite loops and other mistakes. So here is our first question:

What is the condition that ends the loop?

This question usually can be answered through a close examination of the problem statement. The following table lists some examples:

Now we need statements that make sure the loop gets started correctly and statements that allow the loop to reach the termination condition. At this point, we ask the next two questions:

How should the condition be initialized?

How should the condition be updated?

The answers to these questions depend on the type of termination condition.

Count-Controlled Loops

If the loop is count controlled, we initialize the condition by giving the loop control variable an initial value. For count-controlled loops in which the loop control variable is also an iteration counter, the initial value is usually 1. If the process requires the counter to run through a specific range of values, the initial value should be the lowest value in that range.

The condition is updated by increasing the value of the counter by 1 for each iteration. (Occasionally, you may come across a problem that requires a counter to count from some value down to a lower value. In this case, the initial value is the greater value, and the counter is decremented by 1 for each iteration.) So, for count-controlled loops that use an iteration counter, these are the answers to the key questions:

Initialize the iteration counter to 1.

Increment the iteration counter at the end of each iteration.

If the loop is controlled by a variable that is counting an event within the loop, the control variable is usually initialized to 0 and is incremented each time the event occurs. For count-controlled loops that use an event counter, these are the answers to the key questions:

Initialize the event counter to 0.

Increment the event counter each time the event occurs.

Sentinel-Controlled Loops

In sentinel-controlled loops, a priming read may be the only initialization necessary. If the source of input is a file rather than the keyboard, it may also be necessary to open the file in preparation for reading. To update the condition, a new value is read at the end of each iteration. So, for sentinel-controlled loops, we answer our key questions this way:

Open the file, if necessary, and input a value before entering the loop (priming read).

Input a new value for processing at the end of each iteration.

EOF-Controlled Loops

EOF-controlled loops require the same initialization as sentinel-controlled loops. You must open the file, if necessary, and perform a priming read. Updating the loop condition happens implicitly; the stream state is updated to reflect success or failure every time a value is input. However, if the loop doesn't read any data, it can never reach EOF; thus updating the loop condition means the loop must keep reading data.

Flag-Controlled Loops

In flag-controlled loops, the Boolean flag variable must be initialized to true or false and then updated when the condition changes.

Initialize the flag variable to true or false, as appropriate.

Update the flag variable as soon as the condition changes.

In a flag-controlled loop, the flag variable essentially remains unchanged until it is time for the loop to end. Then the code detects some condition within the process being repeated that changes the value of the flag (through an assignment statement). Because the update depends on what the process does, sometimes we may have to design the process before we can decide how to update the condition.

Designing the Process Within the Loop

Once we've selected the type of looping structure, we can fill in the details of the process. In designing the process, we first must decide what we want a single iteration to do. Assume for a moment that the process will execute only once. Which tasks must the process perform?

What is the process being repeated?

To answer this question, we have to take another look at the problem statement. The definition of the problem may require the process to sum up data values or to keep a count of data values that satisfy some test. For example:

Count the number of integers in the file howMany.

This statement tells us that the process to be repeated is a counting operation.

Here's another example:

Read a stock price for each business day in a week and compute the average price.

In this case, part of the process involves reading a data value. We conclude from our knowledge of how an average is computed that this process must also involve summing the data values.

In addition to counting and summing, another common loop process is reading data, performing a calculation, and writing out the result. Many other operations can appear in looping processes. We've mentioned only the simplest here; we look at some other processes later on.

After we've determined the operations to be performed if the process is executed only once, we design the parts of the process that are necessary for it to be repeated correctly. We often have to add some steps to account for the fact that the loop executes more than once. This part of the design typically involves initializing certain variables before the loop and then reinitializing or updating them before each subsequent iteration, and it leads to our next two questions:

How should the process be initialized?

How should the process be updated?

For example, if the process within a loop requires that several different counts and sums be performed, each must have its own statements to initialize variables, increment counting variables, or add values to sums. Just deal with each counting or summing operation by itself—that is, first write the initialization statement, and then write the incrementing or summing statement. After you've done this for one operation, go on to the next.

The Loop Exit

When the termination condition occurs and the flow of control passes to the statement following the loop, the variables used in the loop still contain values. If the cin stream has been used, the reading marker has also been left at some position in the stream. Or maybe an output file has new contents. If these variables or files are used later in the program, the loop must leave them in an appropriate state. Thus the final step in designing a loop is answering this question:

What is the state of the program on exiting the loop?

To answer this question, we have to consider the consequences of our design and doublecheck its validity. For example, suppose we've used an event counter and that later processing depends on the number of events. It's important to make sure (with an algorithm walk-through) that the value left in the counter is the exact number of events—that it is not off by 1. Off-by-one bugs are sometimes referred to as OBOBs.

Look at this code segment:

commaCount = 1;       // This code is incorrect
cin.get(inChar);
while (inChar != '
')
{
  if (inChar == ',')
    commaCount++;
  cin.get(inChar);
}
cout << commaCount << endl;

This loop reads characters from an input line and counts the number of commas on the line. However, when the loop terminates, commaCount equals the actual number of commas plus 1 because the loop initializes the event counter to 1 before any events take place. By determining the state of commaCount at loop exit, we've detected a flaw in the initialization. commaCount should be initialized to 0.

Designing correct loops depends as much on experience as it does on the application of design methodology. At this point, you may want to read through the Problem-Solving Case Study at the end of the chapter to see how the loop design process is applied to a real problem.

6.5 Nested Logic

In Chapter 5, we described nested If statements. It's also possible to nest While statements. Both While and If statements contain statements and are themselves statements. As a consequence, the body of a While statement or the branch of an If statement can contain other While and If statements. By nesting, we can create complex control structures.

Suppose we want to extend our code for counting commas on one line, repeating it for all the lines in a file. We put an EOF-controlled loop around it:

cin.get(inChar);              // Initialize outer loop
while (cin)                   // Outer loop test
{
  commaCount = 0;             // Initialize inner loop
                              // (Priming read is taken care of
                              // by outer loop's priming read)
  while (inChar != '
')      // Inner loop test
  {
    if (inChar == ',')
      commaCount++;
    cin.get(inChar);          // Update inner termination condition
  }
  cout << commaCount << endl;
  cin.get(inChar);            // Update outer termination    condition
}

In this code, we omitted the priming read for the inner loop. The priming read for the outer loop has already “primed the pump.” It would be a mistake to include another priming read just before the inner loop, because the character read by the outer priming read would be destroyed before we could test it.

Let's examine the general pattern of a simple nested loop. The dots represent places where the processing and update may take place in the outer loop.

Notice that each loop has its own initialization, test, and update operation. It's possible for an outer loop to do no processing other than to execute the inner loop repeatedly. Conversely, the inner loop might be just a small part of the processing done by the outer loop; there could be many statements preceding or following the inner loop.

Let's look at another example. For nested count-controlled loops, the pattern looks like this (where outCount is the counter for the outer loop, inCount is the counter for the inner loop, and limit1 and limit2 are the number of times each loop should be executed):

Here, both the inner and outer loops are count-controlled loops, but the pattern can be used with any combination of loops.

The following program shows a count-controlled loop nested within an event-controlled loop. The outer loop inputs an integer value telling how many asterisks to print out across a row of the screen.

Output:

To see how this code works, let's trace its execution with the data values shown in the sample session. Notice that the event that controls the loop is the keying of a letter when cin expects a number. This puts the input stream into the fail state, returning false when tested.

We'll keep track of the variables starCount and loopCount, as well as the logical expressions. To do so, we've numbered each line within the loops (except those containing only a left or right brace). As we trace the program, we indicate the first execution of line 3 by 3.1, the second by 3.2, and so on. Each loop iteration is enclosed by a large brace, and true and false are abbreviated as T and F (see Table 6.1).

Table 6.1Code Trace

Because starCount and loopCount are variables, their values remain the same until they are explicitly changed, as indicated by the repeating values in Table 6.1. The values of the logical expressions cin and loopCount <= starCount exist only when the test is made. We indicate this fact with dashes in those columns at all other times.

Designing Nested Loops

To design a nested loop, we begin with the outer loop. The process being repeated includes the nested loop as one of its steps. Because that step is more complex than a single statement, our functional decomposition methodology tells us to make it a separate module. We can come back to it later and design the nested loop just as we would any other loop.

For example, here's the design process for the preceding code segment:

1. What is the condition that ends the loop? 'Q' entered.

2. How should the condition be initialized? A priming read should be performed before the loop starts.

3. How should the condition be updated? An input statement should occur at the end of each iteration.

4. What is the process being repeated? Using the value of the current input integer, the code should print that many asterisks across one output line.

5. How should the process be initialized? No initialization is necessary.

6. How should the process be updated? A sequence of asterisks is output and then a newline character is output. There are no counter variables or sums to update.

7. What is the state of the program on exiting the loop? The cin stream is in the fail state (because the program encountered a letter when an integer was expected), starCount contains the last integer read from the input stream, and the rows of asterisks have been printed along with a concluding message.

From the answers to these questions, we can write this much of the algorithm:
 
 

 Read starCount
 WHILE Stream okay
   Print starCount asterisks
   Output newline
   Prompt
   Read starCount
 Print “Goodbye”

After designing the outer loop, it's obvious that the process in its body (printing a sequence of asterisks) is a complex step that requires us to design an inner loop. So we repeat the methodology for the corresponding lower-level module:

1. What is the condition that ends the loop? An iteration counter exceeds the value of starCount.

2. How should the condition be initialized? The iteration counter should be initialized to 1.

3. How should the condition be updated? The iteration counter is incremented at the end of each iteration.

4. What is the process being repeated? The code should print a single asterisk on the standard output device.

5. How should the process be initialized? No initialization is needed.

6. How should the process be updated? No update is needed.

7. What is the state of the program on exiting the loop? A single row of asterisks has been printed, the writing marker is at the end of the current output line, and loopCount contains a value one greater than the current value of starCount.

Now we can write the algorithm:
 
 

Read starCount
WHILE Stream okay
   Set loopCount = 1
   WHILE loopCount <= starCount
     Print '*'
     Increment loopCount
   Output newline
   Read starCount
Print “Goodbye”

Of course, nested loops themselves can contain nested loops (called doubly nested loops), which can also contain nested loops (triply nested loops), and so on. You can use this design process for any number of levels of nesting. The trick is to defer details by using the functional decomposition methodology—that is, focus on the outermost loop first and treat each new level of nested loop as a module within the loop that contains it.

It's also possible for the process within a loop to include more than one loop. For example, we rewrote the checkerboard program earlier in this chapter using a loop. Now let's rewrite it again, this time using two loops nested within the outer loop. Here is the algorithm followed by the code.

Set up whiteRow
Set up blackRow
Set loopCount to 0
WHILE loopCount < 4
   Print whiteRows
   Print blackRows
   Increment loopCount

Set loopCount2 to 0
WHILE loopCount2 < 5
   Print whiteRow
   Increment loopCount2

Set loopCount2 to 0
WHILE loopCount 2 < 5
  Print blackRow
  Increment loopCount2

Problem-Solving Case Study

Recording Studio Design

PROBLEM: You've gone to work for a consulting firm that specializes in converting existing rooms into recording studios. Your employers have asked you to write a program that inputs a set of loudness measurements for a room and prints out basic statistics. The measurements are made by playing a series of 12 different tones, and recording the readings from a sound-level meter onto a file. The meter readings range from 50 to 126 decibels (a measure of loudness). Your program, however, is to output the measurements relative to the first tone—that is, to show how much each individual reading differs from the first. After all the data has been read, the program is to print out the highest and lowest readings.

INPUT: Twelve real numbers, representing the meter readings, on file acoustic.dat.

OUTPUT

The 12 input values (echo print) and their values relative to the first reading

At the end of the program, the actual value, relative value, and sequence number of both the highest reading and the lowest
 

DISCUSSION: This problem is easy to calculate by hand. We simply scan the list, subtracting the first value from each value in the list. As we scan the list, we also keep track of which value from the list is the highest and which is the lowest.

How do we translate this process into an algorithm? Let's take a closer look at what we are doing. To find the largest number in a list, we compare the first and second numbers and remember the larger one. Then we compare that number with the third one, remembering the larger number. We repeat the process for all of the numbers, and the one we remember at the end is the largest. We use the same process to find the smallest number, except that we remember the smaller number instead of the larger one.

Consider a sample data set:

The maximum reading for this data set was number 6 at 89.6 decibels. The lowest was reading 12 at 73.5 decibels.

“Scan the list” in our by-hand algorithm translates into a loop. Now that we understand the process, let's design the looping algorithm using our checklist.

1. What is the condition that ends the loop? Because there are exactly 12 values in a set of readings, we use a counter to control the loop. When it exceeds 12, the loop exits.

2. How should the condition be initialized? The first value will be input before the loop because it is a special case—it is the value that is subtracted from all the other values to get their relative values. Also, its relative value is automatically 0.0. Thus the first iteration of the loop gets the second value, so the counter will start at 2.

3. How should the condition be updated? The counter should be incremented at the end of each iteration.

4. What is the process being repeated? The process reads a value, echo prints it, subtracts the first value from the new value, prints the result, and checks whether the new value should replace the current high or low value.

5. How should the process be initialized? The first number must be read in. Its relative value is automatically printed as 0.0. It is the initial high and low, and it is also saved as the base reading. The sequence number for both the high and low values will be set to 1 and their relative values will be 0.0.

6. How should the process be updated? In each iteration, a new current reading is input. If the current reading is greater than high, it replaces the current high. If the current reading is lower than the current low, then it becomes the new low. We must also save the reading number of the highest and lowest values, and their relative values.

7. What is the state of the program on exiting the loop? Twelve readings have been input and echo printed together with 12 relative values. The loop control variable equals 13. high contains the greatest value read, highNumber the number of that value, and highRelative the relative value for that reading. low contains the lowest value, lowNumber holds the number of that reading, and lowRelative has the corresponding relative value.
 

ASSUMPTIONS: At least 12 real numbers will be input, and all will be within the proper range.
 

Initialize process
Initialize loop ending condition
WHILE readingNumber <= 12 DO
  Update process
  Update ending condition
Print high and low readings
Close file

Open input file
IF not opened okay
   Write error message
   Return 1
Print heading for output
Get baseValue
Print readingNumber 1, baseValue, relativeValue 0.0
Set high to baseValue
Set highNumber to 1
Set highRelative to 0.0
Set low to baseValue
Set lowNumber to 1
Set lowRelative to 0.0

Set readingNumber to 2

Get current
Set relative to current - baseValue
Print readingNumber, current, relative
Check for new high
Check for new low

Increment readingNumber

Print 'Highest reading number is ', highNumber
Print 'Highest reading is ', high
Print 'Highest relative value is ', highRelative
Print 'Lowest reading number is ', lowNumber
Print 'Lowest reading is ', low
Print 'Lowest relative value is ', lowRelative

IF current > high
   Set high to current
   Set highNumber to readingNumber
   Set highRelative to relative

IF current < low
   Set low to current
   Set lowNumber to readingNumber
   Set lowRelative to relative

MODULE STRUCTURE CHART

Here is the output:

Here is the output:

Now that you have written the program, you call the president of the consulting firm and fax her the results. After studying the results, she is silent for a moment. “Oh. Right. I'm sorry,” she says, “but I told you to keep track of the wrong value. We're not interested in the lowest value, but in the lowest dip in the readings. You see, the last value is almost always the lowest because it's the lowest tone, and we know that most rooms respond poorly to bass notes. There's nothing we can do about that. But the lowest dip in the readings often occurs with a higher tone, and that's usually a sign of a problem that we can fix. Can you change the program to output the lowest dip?” You confirm that a dip is a reading followed by a higher reading.

Now you have to figure out how to recognize a dip in the readings. You draw some graphs with random squiggles on them and pick out the lowest dips by hand. Then you make up some data sets that would generate the graphs. You find that a dip is usually a series of decreasing values followed by increasing values. But it can also just be a series of equal values followed by greater values. The bottom of a dip is merely the lowest value before values start increasing. You know how to keep track of a lowest value, but how do you tell if it is followed by a greater value?

The answer is that you check for this condition after the next value is input. That is, when you read in a new value, you check whether the preceding value was lower. If it was, then you check whether it was the lowest value input so far. You've seen the algorithm for keeping track of a previous value—now you just have to add it to the program.

Now we can return to the checklist and see what must change. The control of the loop stays the same; only the process changes. Thus we can skip the first three questions.

4. What is the process being repeated? It is the same as before, except where we check for the lowest value. Instead, we first check whether the preceding value is less than the current value. If it is, then we check whether preceding should replace the lowest value so far. In replacing the lowest value, we must assign readingNumber minus one to lowNumber, because the dip occurred with the previous reading. We could also keep track of the previous value of readingNumber, but it is easier to calculate it.

5. How should the process be initialized? The change here is that we must initialize preceding. We can set it equal to the first value. We also have to initialize the precedingRelative value to 0.0.

6. How should the process be updated? We add steps to set preceding equal to current at the end of the loop, and to save Relative in precedingRelative for use in the next iteration.

7. What is the state of the program on exiting the loop? At this point, preceding holds the last value input and precedingRelative holds the last relative value computed. low holds the value of the lowest dip, lowNumber contains the reading number of the lowest dip, and lowRelative is the difference between the lowest dip and the first value.

Now let's look at the modules that have changed. We'll use highlighting to indicate the steps that are different:

Open input file
If not opened OK
   Write error message
   Return 1
Print heading for output
Get baseValue
Print readingNumber 1, baseValue, relativeValue 0.0
Set preceding to baseValue
Set precedingRelative to 0.0
Set high to baseValue
Set highNumber to 1
Set highRelative to 0.0
Set low to baseValue
Set lowNumber to 1
Set lowRelative to 0.0

Prompt for current
Get current
Set relative to current - baseValue
Print readingNumber, current, relative
Check for new high
Check for new low
Set preceding to current
Set precedingRelative to relative

Print 'Highest reading number is ', highNumber
Print 'Highest reading is ', high
Print 'Highest relative value is ', highRelative
Print 'Lowest dip is number ', lowNumber
Print 'Lowest dip reading is ', low
Print 'Lowest relative dip is ', lowRelative

IF current > preceding
   IF preceding < low
      Set low to preceding
      Set lowNumber to readingNumber - 1
      Set lowRelative to precedingRelative

Here's the new version of the program:

Here is the output:

Testing and Debugging

Loop-Testing Strategy

Even if a loop has been properly designed and verified, it is still important to test it rigorously: The chance of an error creeping in during the implementation phase is always present. Because loops allow us to input many data sets in one run, and because each iteration may be affected by preceding ones, the test data for a looping program is usually more extensive than that for a program with just sequential or branching statements. To test a loop thoroughly, we must check for the proper execution of both a single iteration and multiple iterations.

Remember that a loop has seven parts (corresponding to the seven questions in our checklist). A test strategy must test each part. Although all seven parts aren't implemented separately in every loop, the checklist reminds us that some loop operations serve multiple purposes, each of which should be tested. For example, the incrementing statement in a count-controlled loop may be updating both the process and the ending condition, so it's important to verify that it performs both actions properly with respect to the rest of the loop.

To test a loop, we try to devise data sets that could cause the variables to go out of range or leave the files in improper states that violate either the loop postcondition (an assertion that must be true immediately after loop exit) or the postcondition of the module containing the loop.

It's also good practice to test a loop for four special cases: (1) when the loop is skipped entirely, (2) when the loop body is executed just once, (3) when the loop executes some normal number of times, and (4) when the loop fails to exit.

Statements following a loop often depend on its processing. If a loop can be skipped, those statements may not execute correctly. If it's possible to execute a single iteration of a loop, the results can show whether the body performs correctly in the absence of the effects of previous iterations; this strategy can be very helpful when you're trying to isolate the source of an error. Obviously, it's important to test a loop under normal conditions, with a wide variety of inputs. If possible, you should test the loop with real data in addition to mock data sets. Count-controlled loops should be tested to confirm they execute exactly the right number of times. Finally, if there is any chance that a loop might never exit, your test data should try to make that happen.

Testing a program can be as challenging as writing it. To test a program, you need to step back, take a fresh look at what you've written, and then attack it in every way possible to make it fail. This isn't always easy to do, but it's necessary if your programs are going to be reliable. (A reliable program is one that works consistently and without errors regardless of whether the input data is valid or invalid.)

Test Plans Involving Loops

In Chapter 5, we introduced formal test plans and discussed the testing of branches. Those guidelines still apply to programs with loops, but here we provide some additional guidelines that are specific to loops.

Unfortunately, when a loop is embedded in a larger program, it may be difficult to control and observe the conditions under which the loop executes using test data and output alone. In some cases we must use indirect tests. For example, if a loop reads floating-point values from a file and prints their average without echo printing those values, you cannot tell directly that the loop processes all the data—if the data values in the file are all the same, then the average appears correct as long as even one of them is processed. You must construct the input file so that the average is a unique value that can be arrived at only by processing all the data.

To simplify our testing of such loops, we would like to observe the values of the variables associated with the loop at the start of each iteration. How can we observe the values of variables while a program is running? Two common techniques to the use the system's debugger program and to include extra output statements designed solely for debugging purposes. We discuss these techniques in the “Testing and Debugging Hints” section.

Now let's look at some test cases that are specific to the different types of loops that we've seen in this chapter.

Count-Controlled Loops

When a loop is count controlled, you should include a test case that specifies the output for all the iterations. It may help to add an extra column to the test plan that lists the iteration number. If the loop reads data and outputs a result, then each input value should produce a different output to make it easier to spot errors. For example, in a loop that is supposed to read and print 100 data values, it is easier to tell that the loop executes the correct number of iterations when the values are 1, 2, 3, …, 100 than when they are all the same.

If the program inputs the iteration count for the loop, you need to test the cases in which an invalid count, such as a negative number, is input (an error message should be output and the loop should be skipped), a count of 0 is input (the loop should be skipped), a count of 1 is input (the loop should execute once), and some typical number of iterations is input (the loop should execute the specified number of times).

Event-Controlled Loops

In an event-controlled loop, you should test the situation in which the event occurs before the loop, in the first iteration, and in a typical number of iterations. For example, if the event is that EOF occurs, then try test data consisting of an empty file, a file with one data set, and another file with several data sets. If your testing involves reading from test files, you should attach printed copies of the files to the test plan and identify each in some way so that the plan can refer to them. It also helps to identify where each iteration begins in the Input and Expected Output columns of the test plan.

When the event is the input of a sentinel value, you need the following test cases: The sentinel is the only data set, the sentinel follows one data set, and the sentinel follows a typical number of data sets. Given that sentinel-controlled loops involve a priming read, it is especially important to verify that the first and last data sets are processed properly.

Testing and Debugging Hints

1. Plan your test data carefully to test all sections of a program.

2. Beware of infinite loops, in which the expression in the While statement never becomes false. The symptom: The program doesn't stop. If you are on a system that monitors the execution time of a program, you may see a message such as “TIME LIMIT EXCEEDED.”
    If you have created an infinite loop, check your logic and the syntax of your loops. Be sure no semicolon appears immediately after the right parenthesis of the While condition:

while (Expression); // Wrong
Statement

This semicolon causes an infinite loop in most cases; the compiler thinks the loop body is the null statement (the do-nothing statement composed solely of a semicolon). In a count-controlled loop, make sure the loop control variable is incremented within the loop. In a flag-controlled loop, make sure the flag eventually changes.

As always, watch for the = versus == problem in While conditions as well as in If conditions. The line

while (someVar = 5) // Wrong (should be ==)

produces an infinite loop. The value of the assignment (not relational) expression is always 5, which is interpreted as true.

3. Check the loop termination condition carefully and be sure that something in the loop causes it to be met. Watch closely for values that cause one iteration too many or too few (the “off-by-one-bug” syndrome).

4. Remember to use the get function rather than the >> operator in loops that are controlled by detection of a newline character.

5. Perform an algorithm walk-through to verify that all of the appropriate preconditions and postconditions occur in the right places.

6. Trace the execution of the loop by hand with a code walk-through. Simulate the first few passes and the last few passes very carefully to see how the loop really behaves.

7. Use a debugger if your system provides one. A debugger is a program that runs your program in “slow motion,” allowing you to execute one instruction at a time and to examine the contents of variables as they change. If you haven't already done so, check whether a debugger is available on your system.

8. If all else fails, use debug output statements—output statements inserted into a program to help debug it. They output messages that indicate the flow of execution in the program or report the values of variables at certain points in the program.
    For example, if you want to know the value of variable beta at a certain point in a program, you could insert this statement:

cout << “beta = “ << beta << endl;

If this output statement appears in a loop, you will get as many values of beta output as there are iterations of the body of the loop.

   After you have debugged your program, you can remove the debug output statements or just precede them with // so that they'll be treated as comments. (This practice is referred to as commenting out a piece of code.) You can remove the double slashes if you need to use the statements again.

9. An ounce of prevention is worth a pound of debugging. Use the checklist questions to design your loop correctly at the outset. It may seem like extra work, but it pays off in the long run.

Summary

The While statement is a looping construct that allows a program to repeat a statement as long as the value of an expression is true. When the value of the While expression becomes false, the body of the loop is skipped and execution continues with the first statement following the loop.

With the While statement, you can construct several types of loops that you will use again and again. These types of loops are classified into one of two categories: count-controlled loops and event-controlled loops.

In a count-controlled loop, the loop body is repeated a specified number of times. You initialize a counter variable right before the While statement. This loop control variable is then tested against the limit in the While expression. The last statement in the loop body increments the control variable.

Event-controlled loops continue executing until something inside the body signals that the looping process should stop. Event-controlled loops include those that test for a sentinel value in the data, for end-of-file, or for a change in a flag variable.

Sentinel-controlled loops are input loops that use a special data value as a signal to stop reading. EOF-controlled loops are loops that continue to input (and process) data values until no more data remains. To implement them with a While statement, you must test the state of the input stream by using the name of the stream object as if it were a Boolean variable. The test yields false when there are no more data values. A flag is a variable that is set in one part of the program and tested in another part of the same program. In a flagcontrolled loop, you must set the flag before the loop begins, test it in the While expression, and change it somewhere in the body of the loop.

Counting is a looping operation that keeps track of how many times a loop is repeated or how many times some event occurs. This count can be used in computations or to control the loop. A counter is a variable that is used for counting. It may take the form of a loop control variable in a count-controlled loop, an iteration counter in a counting loop, or an event counter that counts the number of times a particular condition occurs in a loop.

Summing is a looping operation that keeps a running total of certain values. It is like counting in that the variable that holds the sum is initialized outside the loop. The summing operation, however, adds up unknown values; the counting operation adds a constant (1) to the counter each time.

When you design a loop, you should consider seven points: how the termination condition is initialized, tested, and updated; how the process in the loop is initialized, performed, and updated; and the state of the program upon exiting the loop. By answering the checklist questions, you can bring each of these points into focus.

To design a nested loop structure, begin with the outermost loop. When you get to where the inner loop must appear, make it a separate module and come back to its design later.

The process of testing a loop is based on the answers to the checklist questions and the patterns the loop might encounter (for example, executing a single iteration, multiple iterations, an infinite number of iterations, or no iterations at all).

Quick Check

1. What are the four phases of loop execution? (p. 242)

2. How is a flag-controlled loop like a sentinel-controlled loop, and how do the two types of loops differ? (pp. 245–251)

3. Does averaging a set of values that are input by a loop involve summing, counting, or both? (pp. 251–255)

4. Which type of loop would you use to read a file of drivers' license numbers until a specific number is input? (pp. 259–260)

5. Write a While statement that exits when the int variable count is greater than 10 or the Boolean flag found is true. (pp. 243–251)

6. Write the initialization and update portions for the termination condition of the loop in Question 5. The variable found becomes true when the int variable inData contains 0. The count starts at 1 and is incremented in each iteration. (pp. 259–260)

7. Add a test for the condition end-of-file on cin to the loop in Question 6, and add statements to the loop that perform a priming read and an updating read of inData from cin. (pp. 248–250)

8. Add initialization and update operations to the loop in Question 7 that cause it to count the occurrences of the value 1 that are input to variable inData, and to sum all of the values read into inData. (p. 252)

9. How would you extend the loop from Question 8 so that it would be repeated in its entirety five times? (pp. 266–267)

10. How would you test a looping program that reads hourly temperatures from a file and outputs the daily average? (p. 285)

Answers

1. Entry, iteration, test, exit. 2. Both types of loops exit when an event occurs. The sentinel-controlled loop tests for the event at the start of each iteration, while the flag-controlled loop checks for the event in the middle of the iteration, setting a flag to be tested at the start of the next iteration. 3. Both. 4. An event-controlled loop. (The events would be the input of the number, or reaching end-of-file). 5. while (count <= 10 && !found)

6. count = 1;
   found = false;
   while (count <= 10 && !found)
   {
     count++;
     found = inData == 0;
   }
7. count = 1;
   found = false;
   cin >> inData;
   while (count <= 10 && !found && cin)
   {
     count++;
     found = inData == 0;
     cin >> inData;
   }
8. onesCount = 0;
   sum = 0;
   count = 1;
   found = false;
   cin >> inData;
   while (count <= 10 && !found && cin)
   {
     if (inData == 1)
       onesCount++;
     sum = sum + inData;
     count++;
     found = inData == 0;
     cin >> inData;
   }

9. Nest it within a counting loop that counts from 1 to 5. 10. Run the program with an empty file, a file with 24 input values, a file with fewer than 24 input values, and a file with more than 24 input values. Test the program with 24 input values all the same, and with 24 values that differ so that omitting any of them results in an average that's different from the average of all 24.

Exam Preparation Exercises

1. The While statement exits when the termination condition becomes true. True or false?

2. The body of the While statement is always executed at least once. True or false?

3. Using a block as the body of the While statement enables us to place any number of statements within a loop. True or false?

4. Match the following list of terms with the definitions given below.

a. Loop entry.

b. Iteration.

c. Loop test.

d. Loop exit.

e. Termination condition.

f. Count-controlled loop.

g. Event-controlled loop.

h. Iteration counter.

i. Event counter.

i. A loop that executes a specified number of times.

ii. When the flow of control reaches the first statement inside a loop.

iii. A variable that is incremented each time a particular condition is encountered.

iv. When the decision is made whether to begin a new iteration or to exit.

v. A loop that exits when a specific condition is encountered.

vi. The condition that causes the loop to exit.

vii. A variable that is incremented with each iteration of a loop.

viii. When control passes to the statement following the loop.

iv. An individual pass through a loop.

5. How many times does the following loop execute, and what is its output?

count = 1;
while (count <= 12)
{
  cout << count << endl;
  count++;
}

6. How many times does the following loop execute, and what is its output?

count = 0;
while (count <= 11)
{
  cout << count << “, “;
  count++;
}

7. How many times does the following loop execute, and what is its output?

count = 1;
while (count < 13)
{
  cout << “$” << count << “.00” << endl;
  count++;
}

8. What does the following nested loop structure output?

count = 1;
while (count <= 11)
{
  innerCount = 1
  while (innerCount <= (12 - count) / 2)
  {
    cout << “ “;
    innerCount++;
  }
  innerCount = 1;
  while (innerCount <= count)
  {
    cout << “@”;
    innerCount++;
  }
  cout << endl;
  count++;
}

9. What does the following nested loop structure output?

count = 1;
while (count <= 10)
{
  innerCount = 1;
  while (innerCount <= 10)
  {
    cout << setw(5) << count * innercount;
    innerCount++;
  }
  cout << endl;
  count++;
}

10. The following loop is supposed to sum all of the input values on file indata. What's wrong with it? Change the code so that it works correctly.

sum = 0;
indata >> number;
while (indata)
{
  indata >> number;
  sum = sum + number;
}

11. Which sentinel value would you choose for a program that reads names as strings?

12. The following code segment is supposed to write out the odd numbers from 1 to 19.
What does it actually output? Change the code so that it works correctly.

number = 1;
while (number < 10)
{
  number++;
  cout << number * 2 - 1 << “ “;
}

13. Priming reads aren't necessary when a loop is controlled by a sentinel value. True or false?

14. What are the seven questions that must be answered to design a loop?

15. The following code segment is supposed to output the average of the five numbers on each input line, for all of the lines in the file. Instead, it simply outputs the sum of all of the numbers in the file. What's wrong with the code segment? Change the code so that it works correctly.

sum = 0;
while (indata)
{
  count = 1;
  while (count <= 5 && indata)
  {
    cin >> number;
    sum = sum + number;
  }
  cout << sum / count << endl;
}

Programming Warm-Up Exercises

1. Write a code segment using a While loop that outputs the numbers from 210 to 10.

2. Write a code segment using a While loop that sums the integers, counting up from 1, and stops when the sum is greater than 10,000, printing out the integer that was most recently added to the sum.

3. Write a looping code segment that takes as input up to 20 integer scores from file indata, and outputs their average. If the file contains fewer than 20 scores, the segment should still output the correct average. If the file contains more than 20 scores, the additional numbers should be ignored. Be sure to consider what happens if the file is empty.

4. Write a code segment that reads lines of text from file chapter6, and outputs the number of lines in the file that contain the string “code segment”.

5. Write a code segment that reads a string from cin. The string should be one of the following: “Yes”, “No”, “yes”, or “no”. If it is not, the user should be prompted to input an appropriate response, and the process should repeat. Once a valid response is received, the bool variable yes should be assigned true if the response is “Yes” or “yes” and false if the response is “No” or “no”.

6. Write a code segment that prints the days of a month in calendar format. The day of the week on which the month begins is represented by an int variable startDay. When startDay is zero, the month begins on a Sunday. The int variable days contains the number of days in the month. Print a heading with the days of the week as the first line of output. The day numbers should be neatly aligned under these column headings.

7. We could extend the code from Exercise 6 to print a calendar for a year by nesting it within a loop that repeats the code 12 times.

a. Which formula would you use to compute the new start day for the next month?

b. Which additional information would you need to print the calendar for each month?

8. Write a code segment that reads all of the characters on file textData, and then outputs the percentage of the characters that are the letter 'z'.

9. Change the code segment in Exercise 8 so that it stops reading either at the end of the file or after 10,000 characters have been input.

10. Write a code segment that outputs the Fibonacci numbers that are less than 30,000. Each Fibonacci number is the sum of its two predecessors. The first two Fibonacci numbers are 1 and 1. Thus, the sequence begins with

1, 1, 2, 3, 5, 8, 13, 21, 34,…

Output each number on a separate line.

11. Modify the code segment in Exercise 10 so that it also outputs the position of the Fibonacci number in the sequence. For example:

12. Write a code segment that inputs an integer from cin, and then outputs a row of that many stars on cout.

13. How did you answer the checklist questions for Exercise 12?

14. Change the code segment for Exercise 12 to read a series of numbers from file indata, and print a row of stars on cout for each number read. (You can think of this problem as printing a bar graph of a data file.)

15. What sort of test data would you use to test the code segment in Exercise 14?

Programming Problems

1. Design and write a C++ program that inputs a series of 24 hourly temperatures from a file, and outputs a bar chart (using stars) of the temperatures for the day. The temperature should be printed to the left of the corresponding bar, and there should be a heading that gives the scale of the chart. The range of temperatures should be from −30 to 120. Because it is hard to display 150 characters on the screen, you should have each star represent a range of 3 degrees. That way, the bars will be at most 50 characters wide. Here is a partial example, showing the heading, the output for a negative temperature, and the output for various positive temperatures. Note how the temperatures are rounded to the appropriate number of stars.

Temperatures for 24 hours:
   -30        0        30        60        90        120
-20    *******|
  0           |
  1           |
  2           |*
  3           |*
  4           |*
  5           |**
 10           |***
 50           |*****************
100           |*********************************

Use meaningful variable names, proper indentation, and appropriate comments. Thoroughly test the program using your own data sets.

2. The standard deviation of a set of data values gives us a sense of the dispersion of values within their range. For example, a set of test scores with a small standard deviation indicates that most people's scores were very close to the average score. Some instructors use the standard deviation as a way of determining the range of values to assign a particular grade.
   Design and write a C++ program that reads a set of scores from the file scores.dat, and outputs their mean and standard deviation on cout. The formula for the standard deviation is
 

where n is the number of values and x_i represents the individual values. Thus, to compute the standard deviation, you must sum the squares of the individual values, and also square the sum of the values. All of this reading and summing can be done with a single loop, after which the mean and standard deviation of the scores are computed. Be sure to properly label the output. Use meaningful variable names, proper indentation, and appropriate comments. Thoroughly test the program using your own data sets.

3. You are burning some music CDs for a party. You've arranged a list of songs in the order in which you want to play them. However, you would like to maximize your use of space on the CD, which holds 80 minutes of music. To do so, you want to figure out the total time for a group of songs and see how well they fit. Write a design and a C++ program to help you accomplish this task. The data are on file songs.dat. The time is entered as seconds. For example, if a song takes 7 minutes and 42 seconds to play, the data entered for that song would be

462

After all the data has been read, the application should print a message indicating the time remaining on the CD.

    The output should be in the form of a table with columns and headings written on a file. For example:

Song          Song Time             Total Time
Number     Minutes  Seconds     Minutes   Seconds
------     -------  -------     -------   -------
1              5      10           5        10
2              7      42          12        52
5              4      19          17        11
3              4      33          21        44
4             10      27          32        11
6              8      55          41         6
7              5       0          46         6
There are 33 minutes and 54 seconds of space left on the 80-minute CD.

Note that the output converts the input from seconds to minutes and seconds. Use meaningful variable names, proper indentation, and appropriate comments. Thoroughly test the program using your own data sets.

4. A palindrome is a phrase that reads the same both forward and backward. Write a C++ program that reads a line from cin, prints its characters in reverse order on cout, and then pronounces judgment on whether the input line is a palindrome. For example, here are two sample runs of the program:

Enter string: able was I ere I saw elba
able was I ere I saw elba
is a palindrome.
Enter string: madam I'm adam
madam I'm adam
is not a palindrome

Hint: Use the substr function within a loop to extract and print the characters one by one from the string, starting at the end of the string; at the same time, extract the corresponding character starting at the beginning of the string to compare with it.

   Use a prompting message, meaningful variable names, proper indentation, and appropriate comments. Thoroughly test the program using your own data sets.

5. You're working for a company that's building an email list from files of mail messages. Your boss would like you to write a program that reads a file called mail.dat, and that outputs every string containing the @ sign to file addresses.dat. For the purpose of this project, a string is defined as it is by the C++ stream reader—a contiguous sequence of non-whitespace characters. Given the data

From:  [email protected]
Date: Wed, 13 Aug 2003 17:12:33 EDT
Subject: Re: hi
To:  [email protected]
John,
Dave's email is [email protected].
ttyl,
sharon

the program would output the following information on file addresses.dat:

[email protected]
[email protected]
[email protected].

Use meaningful variable names, proper indentation, and appropriate comments. Thoroughly test the program using your own data sets.

Case Study Follow-Up

1. The first version of program Acoustic remembers the reading number of the highest reading. If there are multiple readings with the same value, it remembers only the first one. Change the program so that it remembers the last of these values instead. Hint: You need to add only one character to the program.

2. The second version of program Acoustic keeps track of the lowest dip in the readings. If there are two dips that are equal, it remembers the first one. Change the program so that it remembers the last one.

3. Does the loop in program Acoustic use a priming read?

4. Which type of loop, event-controlled or count-controlled, is used in program Acoustic?

5. The problem for the Case Study states that the readings are on a file. They could equally well have been entered from the keyboard. Change the revised program so that the values are entered in real time.

6. How might you determine whether it is better to enter data from a file or from the keyboard?

7. Discuss how you might go about devising a test plan for program Acoustic.