4.10 Formulating Algorithms: Sentinel-Controlled Iteration

Let’s generalize Section 4.9’s class-average problem. Consider the following problem:

  • Develop a class-averaging program that processes grades for an arbitrary number of students each time it’s run.

In the previous class-average example, the problem statement specified the number of students, so the number of grades (10) was known in advance. In this example, no indication is given of how many grades the user will enter during the program’s execution. The program must process an arbitrary number of grades. How can it determine when to stop the input of grades? How will it know when to calculate and print the class average?

One way to solve this problem is to use a special value called a sentinel value (also called a signal value, a dummy value or a flag value) to indicate “end of data entry.” The user enters grades until all legitimate grades have been entered. The user then types the sentinel value to indicate that no more grades will be entered. Sentinel-controlled iteration is often called indefinite iteration because the number of iterations is not known before the loop begins executing.

Clearly, a sentinel value must be chosen that cannot be confused with an acceptable input value. Grades on a quiz are nonnegative integers, so –1 is an acceptable sentinel value for this problem. Thus, a run of the class-averaging program might process a stream of inputs such as 95, 96, 75, 74, 89 and –1. The program would then compute and print the class average for the grades 95, 96, 75, 74 and 89; since –1 is the sentinel value, it should not enter into the averaging calculation.

4.10.1 Top-Down, Stepwise Refinement: The Top and First Refinement

We approach this class-averaging program with a technique called top-down, stepwise refinement, which is essential to the development of well-structured programs. We begin with a pseudocode representation of the top—a single statement that conveys the overall function of the program:


Determine the class average for the quiz

The top is, in effect, a complete representation of a program. Unfortunately, the top rarely conveys sufficient detail from which to write a C++ program. So we now begin the refinement process. We divide the top into a series of smaller tasks and list these in the order in which they’ll be performed. This results in the following first refinement:


Initialize variables
Input, sum and count the quiz grades
Calculate and print the class average

This refinement uses only the sequence structure—the steps listed should execute in order, one after the other.

Software Engineering Observation 4.2

Each refinement, as well as the top itself, is a complete specification of the algorithm—only the level of detail varies.

4.10.2 Proceeding to the Second Refinement

The preceding Software Engineering Observation is often all you need for the first refinement in the top-down process. To proceed to the next level of refinement—that is, the second refinement—we commit to specific variables. In this example, we need a running total of the numbers, a count of how many numbers have been processed, a variable to receive the value of each grade as it’s entered by the user and a variable to hold the calculated average. The pseudocode statement


Initialize variables

can be refined as follows:


Initialize total to zero
Initialize counter to zero

Only the variables total and counter need to be initialized before they’re used. The variables average and grade (for the calculated average and the user input, respectively) need not be initialized, because their values will be replaced as they’re calculated or input.

The pseudocode statement


Input, sum and count the quiz grades

requires iteration to successively input each grade. We do not know in advance how many grades will be entered, so we’ll use sentinel-controlled iteration. The user enters grades one at a time. After entering the last grade, the user enters the sentinel value. The program tests for the sentinel value after each grade is input and terminates the loop when the user enters the sentinel value. The second refinement of the preceding pseudocode statement is then


Prompt the user to enter the first grade
Input the first grade (possibly the sentinel)
While the user has not yet entered the sentinel
    Add this grade into the running total
    Add one to the grade counter
    Prompt the user to enter the next grade
    Input the next grade (possibly the sentinel)

We simply indent the statements under the While to show that they belong to the While. Again, pseudocode is only an informal program development aid.

The pseudocode statement


Calculate and print the class average

can be refined as follows:


If the counter is not equal to zero
      Set the average to the total divided by the counter
      Print the average
else
      Print “No grades were entered”

We’re careful here to test for the possibility of division by zero—a logic error that, if undetected, would cause the program to fail or produce invalid output. The complete second refinement of the pseudocode for the class-average problem is shown in Fig. 4.11.

Error-Prevention Tip 4.3

According to the C++ standard, the result of division by zero in floating-point arithmetic is undefined. When performing division (/) or remainder (%) calculations in which the right operand could be zero, test for this and handle it (e.g., display an error message) rather than allowing the calculation to proceed.

Fig. 4.11 Class-averaging pseudocode algorithm with sentinel-controlled iteration.

Alternate View

 1   Initialize total to zero
 2   Initialize counter to zero
 3
 4   Prompt the user to enter the first grade
 5   Input the first grade (possibly the sentinel)
 6
 7   While the user has not yet entered the sentinel
 8       Add this grade into the running total
 9       Add one to the grade counter
10       Prompt the user to enter the next grade
11       Input the next grade (possibly the sentinel)
12
13   If the counter is not equal to zero
14       Set the average to the total divided by the counter
15       Print the average
16   else
17       Print “No grades were entered”

In Fig. 4.9 and Fig. 4.11, we included blank lines and indentation in the pseudocode to make it more readable. The blank lines separate the algorithms into their phases and set off control statements; the indentation emphasizes the bodies of the control statements.

The pseudocode algorithm in Fig. 4.11 solves the more general class-average problem. This algorithm was developed after two refinements. Sometimes more are needed.

Software Engineering Observation 4.3

Terminate the top-down, stepwise refinement process when you’ve specified the pseudocode algorithm in sufficient detail for you to convert the pseudocode to C++.

 

Software Engineering Observation 4.4

Some programmers do not use program development tools like pseudocode. They feel that their ultimate goal is to solve the problem on a computer and that writing pseudocode merely delays the production of final outputs. Although this may work for simple and familiar problems, it can lead to serious errors and delays in large, complex projects.

4.10.3 Implementing Sentinel-Controlled Iteration

In Fig. 4.12, the main function implements the pseudocode algorithm of Fig. 4.11. Although each grade entered by the user is an integer, the averaging calculation is likely to produce a number with a decimal point—in other words, a real number or floating-point number (e.g., 7.33, 0.0975 or 1000.12345). The type int cannot represent such a number, so this example must use another type to do so. C++ provides data types float and double to store floating-point numbers in memory. The primary difference between these types is that double variables can typically store numbers with larger magnitude and finer detail (i.e., more digits to the right of the decimal point—also known as the number’s precision). C++ also supports type long double for floating-point values with larger magnitude and more precision than double. We say more about floating-point types in Chapter 5.

Fig. 4.12 Solving the class-average problem using sentinel-controlled iteration.

Alternate View

 1   // Fig. 4.12: ClassAverage.cpp
 2   // Solving the class-average problem using sentinel-controlled iteration.
 3   #include <iostream>
 4   #include <iomanip> // parameterized stream manipulators
 5   using namespace std;
 6
 7   int main() {
 8      // initialization phase
 9      int total{0}; // initialize sum of grades
10      unsigned int gradeCounter{0}; // initialize # of grades entered so far
11
12      // processing phase
13      // prompt for input and read grade from user
14      cout << "Enter grade or -1 to quit: ";
15      int grade;
16      cin >> grade;
17
18      // loop until sentinel value read from user
19      while (grade != -1) {
20         total = total + grade; // add grade to total
21         gradeCounter = gradeCounter + 1; // increment counter
22
23         // prompt for input and read next grade from user
24         cout << "Enter grade or -1 to quit: ";
25         cin >> grade;                         
26      }
27
28      // termination phase
29      // if user entered at least one grade...
30      if (gradeCounter != 0) {
31         // use number with decimal point to calculate average of grades
32         double average{static_cast<double>(total) / gradeCounter};
33
34         // display total and average (with two digits of precision)
35         cout << "
Total of the " << gradeCounter
36            << " grades entered is " << total;
37         cout << setprecision(2) << fixed;
38         cout << "
Class average is " << average << endl;
39      }
40      else { // no grades were entered, so output appropriate message
41         cout << "No grades were entered" << endl;
42      }
43   }

Enter grade or -1 to quit: 97
Enter grade or -1 to quit: 88
Enter grade or -1 to quit: 72
Enter grade or -1 to quit: -1

Total of the 3 grades entered is 257
Class average is 85.67

Recall that integer division produces an integer result. This program introduces a special operator called a cast operator to force the averaging calculation to produce a floatingpoint numeric result. This program also stacks control statements on top of one another (in sequence)—the while statement (lines 19–26) is followed in sequence by an ifelse statement (lines 30–42). Much of the code in this program is identical to that in Fig. 4.10, so we concentrate on the new concepts.

Program Logic for Sentinel-Controlled Iteration vs. Counter-Controlled Iteration

Line 10 initializes gradeCounter to 0, because no grades have been entered yet. Remember that this program uses sentinel-controlled iteration to input the grades. The program increments gradeCounter only when the user enters a valid grade. Line 32 declares double variable average, which stores the class average as a floating-point number.

Compare the program logic for sentinel-controlled iteration in this program with that for counter-controlled iteration in Fig. 4.10. In counter-controlled iteration, each iteration of the while statement (lines 12–18 of Fig. 4.10) reads a value from the user, for the specified number of iterations. In sentinel-controlled iteration, the program prompts for and reads the first value (lines 14 and 16 of Fig. 4.12) before reaching the while. This value determines whether the program’s flow of control should enter the body of the while. If the condition of the while is false, the user entered the sentinel value, so the body of the while does not execute (i.e., no grades were entered). If, on the other hand, the condition is true, the body begins execution, and the loop adds the grade value to the total and increments the gradeCounter (lines 20–21). Then lines 24–25 in the loop body input the next value from the user. Next, program control reaches the closing right brace of the loop body at line 26, so execution continues with the test of the while’s condition (line 19). The condition uses the most recent grade entered by the user to determine whether the loop body should execute again.

The value of variable grade is always input from the user immediately before the program tests the while condition. This allows the program to determine whether the value just input is the sentinel value before the program processes that value (i.e., adds it to the total). If the sentinel value is input, the loop terminates, and the program does not add –1 to the total.

Good Programming Practice 4.3

In a sentinel-controlled loop, prompts should remind the user of the sentinel.

After the loop terminates, the ifelse statement at lines 30–42 executes. The condition at line 30 determines whether any grades were input. If none were input, the ifelse statement’s else part executes and displays the message "No grades were entered".

Braces in a while Statement

Notice the while statement’s block in Fig. 4.12 (lines 19–26). Without the braces, the loop would consider its body to be only the first statement, which adds the grade to the total. The last three statements in the block would fall outside the loop body, causing the computer to interpret the code incorrectly as follows:


while (grade != -1)
   total = total + grade; // add grade to total
gradeCounter = gradeCounter + 1; // increment counter

// prompt for input and read next grade from user
cout << "Enter grade or -1 to quit: ";
cin >> grade;

The preceding code would cause an infinite loop in the program if the user did not input the sentinel -1 at line 16 (before the while statement).

4.10.4 Converting Between Fundamental Types Explicitly and Implicitly

If at least one grade was entered, line 32 of Fig. 4.12


double average{static_cast<double>(total) / gradeCounter};

calculates the average. Recall from Fig. 4.10 that integer division yields an integer result. Even though variable average is declared as a double, if we had written line 32 as


double average{total / gradeCounter};

it would lose the fractional part of the quotient before the result of the division was used to initialize average.

static_cast Operator

To perform a floating-point calculation with integers in this example, you first create temporary floating-point values using the static_cast operator. Line 32 converts a temporary copy of its operand in parentheses (total) to the type in angle brackets (double). The value stored in total is still an integer. Using a cast operator in this manner is called explicit conversion.

Promotions

After the cast operation, the calculation consists of the temporary double copy of total divided by the integer gradeCounter. For arithmetic, the compiler knows how to evaluate only expressions in which the operand types are identical. To ensure this, the compiler performs an operation called promotion (also called implicit conversion) on selected operands. In an expression containing values of data types int and double, C++ promotes int operands to double values. So in line 32, C++ promotes a temporary copy of gradeCounter’s value to type double, then performs the division. Finally, average is initialized with the floating-point result. Section 6.5 discusses the allowed fundamental-type promotions.

Cast Operators for Any Type

Cast operators are available for use with every fundamental type and with class types as well. The operator is formed by following keyword static_cast with a type name in angle brackets (< and >). It’s a unary operator—that is, it has only one operand. C++ also supports unary versions of the plus (+) and minus (-) operators, so that you can write such expressions as -7 or +5. Cast operators have the second highest precedence (Appendix A).

4.10.5 Formatting Floating-Point Numbers

The formatting capabilities in Fig. 4.12 are discussed here briefly and explained in depth in Chapter 13, Stream Input/Output: A Deeper Look.

setprecision Parameterized Stream Manipulator

The call to setprecision (with the argument 2) in line 37


cout << setprecision(2) << fixed;

indicates that floating-point values should be output with two digits of precision to the right of the decimal point (e.g., 92.37). setprecision is a parameterized stream manipulator, because it requires an argument to perform its task. Programs that use these calls must include the header <iomanip> (line 4). The manipulator endl (from the header <iostream>) is a nonparameterized stream manipulator, because it does not require an argument. By default, floating-point values are output with six digits of precision.

fixed Nonparameterized Stream Manipulator

The stream manipulator fixed (line 37) indicates that floating-point values should be output in fixed-point format, as opposed to scientific notation. Scientific notation is a way of displaying a number as a floating-point number between the values of 1.0 and 10.0, multiplied by a power of 10. For instance, the value 3,100.0 would be displayed in scientific notation as 3.1×103. Scientific notation is useful when displaying very large or very small values. Formatting using scientific notation is discussed further in Chapter 13.

Fixed-point formatting forces a floating-point number to display a specific number of digits. Fixed-point formatting also forces the decimal point and trailing zeros to print, even if the value is a whole-number amount, such as 88.00. Without the fixed-point formatting option, 88.00 prints as 88 without the trailing zeros and decimal point.

Rounding Floating-Point Numbers

When the stream manipulators fixed and setprecision are used, the printed value is rounded to the number of decimal positions indicated by setprecision’s argument (2 in this example), although the value in memory remains unaltered. For example, the values 87.946 and 67.543 are output as 87.95 and 67.54, respectively. It’s also possible to force a decimal point to appear by using stream manipulator showpoint. If showpoint is specified without fixed, then trailing zeros will not print. Like endl, the nonparameterized stream manipulators fixed and showpoint require the header <iostream>.

Together, lines 37 and 38 of Fig. 4.12 output the class average rounded to the nearest hundredth and with exactly two digits to the right of the decimal point. The three grades entered during the execution of the program in Fig. 4.12 total 257, which yields the average 85.666… and prints with rounding as 85.67.

4.10.6 Unsigned Integers and User Input

In Fig. 4.10, line 10 declared gradeCounter as an unsigned int, because it stores only non-negative values. Figure 4.10 could have also declared as unsigned int the variables grade, total and average. Grades are normally values from 0 to 100, so the total and average should each be greater than or equal to 0. We declared those variables as ints, however, because we can’t control what the user actually enters—the user could enter negative values. Worse yet, the user could enter a value that’s not even a number. (We’ll show string-processing capabilities later in the book that can be used to check for erroneous inputs.)

Sometimes sentinel-controlled loops use intentionally invalid values to terminate a loop. For example, in line 19 of Fig. 4.12, we terminate the loop when the user enters the sentinel -1 (an invalid grade), so it would be improper to declare variable grade as an unsigned int. As you’ll see, the end-of-file (EOF) indicator—which is often used to terminate sentinel-controlled loops—is also normally implemented internally in the compiler as a negative number.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset