Formulating Algorithms: Sentinel-Controlled Repetition
Formulating Algorithms Sentinel Controlled Repetition
Let us generalize the class average problem. Consider the following problem:
Develop a class average program that processes grades for an arbitrary number of students each time it is 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 the program 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 types grades in until all legitimate grades have been entered. The user then types the sentinel value to indicate that the last grade has been entered. Sentinel-controlled repetition is often called indefinite repetition because the number of repetitions is not known before the loop begins executing.
Clearly, the sentinel value must be chosen so that it cannot be confused with an acceptable input value. Grades on a quiz are normally nonnegative integers, so 1 is an acceptable sentinel value for this problem. Thus, a run of the class average 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.
Common Programming Error 4.9
|
Choosing a sentinel value that is also a legitimate data value is a logic error. |
Developing the Pseudocode Algorithm with Top-Down, Stepwise Refinement: The Top and First Refinement
We approach the class average program with a technique called top-down, stepwise refinement, a technique that is essential to the development of well-structured programs. We begin with a pseudocode representation of the topa 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 (as in this case) rarely conveys sufficient detail from which to write a 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 need to be performed. This results in the following first refinement.
Initialize variables Input, sum and count the quiz grades Calculate and print the total of all student grades and the class average
This refinement uses only the sequence structurethe steps listed should execute in order, one after the other.
Software Engineering Observation 4.4
|
Each refinement, as well as the top itself, is a complete specification of the algorithm; only the level of detail varies. |
Software Engineering Observation 4.5
|
Many programs can be divided logically into three phases: an initialization phase that initializes the program variables; a processing phase that inputs data values and adjusts program variables (such as counters and totals) accordingly; and a termination phase that calculates and outputs the final results. |
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, i.e., 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 is input 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 are 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 are calculated or input.
The pseudocode statement
Input, sum and count the quiz grades
requires a repetition statement (i.e., a loop) that successively inputs each grade. We do not know in advance how many grades are to be processed, so we will use sentinel-controlled repetition. The user enters legitimate grades one at a time. After entering the last legitimate 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)
In pseudocode, we do not use braces around the statements that form the body of the While structure. 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 total of all student grades and 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 total of the grades for all students in the class Print the class average else Print "No grades were entered"
We are careful here to test for the possibility of division by zeronormally a fatal logic error that, if undetected, would cause the program to fail (often called "bombing" or "crashing"). The complete second refinement of the pseudocode for the class average problem is shown in Fig. 4.11.
|
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 total of the grades for all students in the class 16 Print the class average 17 else 18 Print "No grades were entered" |
Common Programming Error 4.10
|
An attempt to divide by zero normally causes a fatal runtime error. |
Error-Prevention Tip 4.3
|
When performing division by an expression whose value could be zero, explicitly test for this possibility and handle it appropriately in your program (such as by printing an error message) rather than allowing the fatal error to occur. |
In Fig. 4.7 and Fig. 4.11, we include some blank lines and indentation in the pseudocode to make it more readable. The blank lines separate the pseudocode algorithms into their various phases, and the indentation emphasizes the control statement bodies.
The pseudocode algorithm in Fig. 4.11 solves the more general class average problem. This algorithm was developed after only two levels of refinement. Sometimes more levels are necessary.
Software Engineering Observation 4.6
|
Terminate the top-down, stepwise refinement process when the pseudocode algorithm is specified in sufficient detail for you to be able to convert the pseudocode to C++. Normally, implementing the C++ program is then straightforward. |
Software Engineering Observation 4.7
|
Many experienced programmers write programs without ever using program development tools like pseudocode. These programmers 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 method might work for simple and familiar problems, it can lead to serious difficulties in large, complex projects. |
Implementing Sentinel-Controlled Repetition in Class GradeBook
Figures 4.12 and 4.13 show the C++ class GradeBook containing member function determineClassAverage that implements the pseudocode algorithm of Fig. 4.11 (this class is demonstrated in Fig. 4.14). Although each grade entered is an integer, the averaging calculation is likely to produce a number with a decimal pointin 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 class must use another type to do so. C++ provides several data types for storing floating-point numbers in memory, including float and double. The primary difference between these types is that, compared to float variables, double variables can store numbers with larger magnitude and finer detail (i.e., more digits to the right of the decimal pointalso known as the number's precision). This program introduces a special operator called a cast operator to force the averaging calculation to produce a floating-point numeric result. These features are explained in detail as we discuss the program.
Figure 4.12. Class average problem using sentinel-controlled repetition: GradeBook header file.
|
1 // Fig. 4.12: GradeBook.h 2 // Definition of class GradeBook that determines a class average. 3 // Member functions are defined in GradeBook.cpp 4 #include // program uses C++ standard string class 5 using std::string; 6 7 // GradeBook class definition 8 class GradeBook 9 { 10 public: 11 GradeBook( string ); // constructor initializes course name 12 void setCourseName( string ); // function to set the course name 13 string getCourseName(); // function to retrieve the course name 14 void displayMessage(); // display a welcome message 15 void determineClassAverage(); // averages grades entered by the user 16 private: 17 string courseName; // course name for this GradeBook 18 }; // end class GradeBook |
Figure 4.13. Class average problem using sentinel-controlled repetition: GradeBook source code file.
(This item is displayed on pages 149 - 151 in the print version)
|
1 // Fig. 4.13: GradeBook.cpp 2 // Member-function definitions for class GradeBook that solves the 3 // class average program with sentinel-controlled repetition. 4 #include 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 using std::fixed; // ensures that decimal point is displayed 9 10 #include // parameterized stream manipulators 11 using std::setprecision; // sets numeric output precision 12 13 // include definition of class GradeBook from GradeBook.h 14 #include "GradeBook.h" 15 16 // constructor initializes courseName with string supplied as argument 17 GradeBook::GradeBook( string name ) 18 { 19 setCourseName( name ); // validate and store courseName 20 } // end GradeBook constructor 21 22 // function to set the course name; 23 // ensures that the course name has at most 25 characters 24 void GradeBook::setCourseName( string name ) 25 { 26 if ( name.length() <= 25 ) // if name has 25 or fewer characters 27 courseName = name; // store the course name in the object 28 else // if name is longer than 25 characters 29 { // set courseName to first 25 characters of parameter name 30 courseName = name.substr( 0, 25 ); // select first 25 characters 31 cout << "Name "" << name << "" exceeds maximum length (25). " 32 << "Limiting courseName to first 25 characters. " << endl; 33 } // end if...else 34 } // end function setCourseName 35 36 // function to retrieve the course name 37 string GradeBook::getCourseName() 38 { 39 return courseName; 40 } // end function getCourseName 41 42 // display a welcome message to the GradeBook user 43 void GradeBook::displayMessage() 44 { 45 cout << "Welcome to the grade book for " << getCourseName() << "! " 46 << endl; 47 } // end function displayMessage 48 49 // determine class average based on 10 grades entered by user 50 void GradeBook::determineClassAverage() 51 { 52 int total; // sum of grades entered by user 53 int gradeCounter; // number of grades entered 54 int grade; // grade value 55 double average; // number with decimal point for average 56 57 // initialization phase 58 total = 0; // initialize total 59 gradeCounter = 0; // initialize loop counter 60 61 // processing phase 62 // prompt for input and read grade from user 63 cout << "Enter grade or -1 to quit: "; 64 cin >> grade; // input grade or sentinel value 65 66 // loop until sentinel value read from user 67 while ( grade != -1 ) // while grade is not -1 68 { 69 total = total + grade; // add grade to total 70 gradeCounter = gradeCounter + 1; // increment counter 71 72 // prompt for input and read next grade from user 73 cout << "Enter grade or -1 to quit: "; 74 cin >> grade; // input grade or sentinel value 75 } // end while 76 77 // termination phase 78 if ( gradeCounter != 0 ) // if user entered at least one grade... 79 { 80 // calculate average of all grades entered 81 average = static_cast< double >( total ) / gradeCounter; 82 83 // display total and average (with two digits of precision) 84 cout << " Total of all " << gradeCounter << " grades entered is " 85 << total << endl; 86 cout << "Class average is " << setprecision( 2 ) << fixed << average 87 << endl; 88 } // end if 89 else // no grades were entered, so output appropriate message 90 cout << "No grades were entered" << endl; 91 } // end function determineClassAverage |
Figure 4.14. Class average problem using sentinel-controlled repetition: Creating an object of class GradeBook (Fig. 4.12Fig. 4.13) and invoking its determineClassAverage member function.
(This item is displayed on pages 151 - 152 in the print version)
|
1 // Fig. 4.14: fig04_14.cpp 2 // Create GradeBook object and invoke its determineClassAverage function. 3 4 // include definition of class GradeBook from GradeBook.h 5 #include "GradeBook.h" 6 7 int main() 8 { 9 // create GradeBook object myGradeBook and 10 // pass course name to constructor 11 GradeBook myGradeBook( "CS101 C++ Programming" ); 12 13 myGradeBook.displayMessage(); // display welcome message 14 myGradeBook.determineClassAverage(); // find average of 10 grades 15 return 0; // indicate successful termination 16 } // end main
|
In this example, we see that control statements can be stacked on top of one another (in sequence) just as a child stacks building blocks. The while statement (lines 6775 of Fig. 4.13) is immediately followed by an if...else statement (lines 7890) in sequence. Much of the code in this program is identical to the code in Fig. 4.9, so we concentrate on the new features and issues.
Line 55 declares the double variable average. Recall that we used an int variable in the preceding example to store the class average. Using type double in the current example allows us to store the class average calculation's result as a floating-point number. Line 59 initializes the variable gradeCounter to 0, because no grades have been entered yet. Remember that this program uses sentinel-controlled repetition. To keep an accurate record of the number of grades entered, the program increments variable gradeCounter only when the user enters a valid grade value (i.e., not the sentinel value) and the program completes the processing of the grade. Finally, notice that both input statements (lines 64 and 74) are preceded by an output statement that prompts the user for input.
Good Programming Practice 4.7
|
Prompt the user for each keyboard input. The prompt should indicate the form of the input and any special input values. For example, in a sentinel-controlled loop, the prompts requesting data entry should explicitly remind the user what the sentinel value is. |
Program Logic for Sentinel-Controlled Repetition vs. Counter-Controlled Repetition
Compare the program logic for sentinel-controlled repetition in this application with that for counter-controlled repetition in Fig. 4.9. In counter-controlled repetition, each iteration of the while statement (lines 5763 of Fig. 4.9) reads a value from the user, for the specified number of iterations. In sentinel-controlled repetition, the program reads the first value (lines 6364 of Fig. 4.13) 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 (line 69). Then lines 7374 in the loop's body input the next value from the user. Next, program control reaches the closing right brace (}) of the body at line 75, so execution continues with the test of the while's condition (line 67). The condition uses the most recent grade input by the user to determine whether the loop's body should execute again. Note that 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 and increments gradeCounter). If the sentinel value is input, the loop terminates, and the program does not add 1 to the total.
After the loop terminates, the if...else statement at lines 7890 executes. The condition at line 78 determines whether any grades were entered. If none were, the else part (lines 8990) of the if...else statement executes and displays the message "No grades were entered" and the member function returns control to the calling function.
Notice the block in the while loop in Fig. 4.13. Without the braces, the last three statements in the body of the loop would fall outside the loop, causing the computer to interpret this code incorrectly, as follows:
// loop until sentinel value read from user 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;
This would cause an infinite loop in the program if the user did not input 1 for the first grade (at line 64).
Common Programming Error 4.11
|
Omitting the braces that delimit a block can lead to logic errors, such as infinite loops. To prevent this problem, some programmers enclose the body of every control statement in braces, even if the body contains only a single statement. |
Floating-Point Number Precision and Memory Requirements
Variables of type float represent single-precision floating-point numbers and have seven significant digits on most 32-bit systems today. Variables of type double represent double-precision floating-point numbers. These require twice as much memory as float variables and provide 15 significant digits on most 32-bit systems todayapproximately double the precision of float variables. For the range of values required by most programs, variables of type float should suffice, but you can use double to "play it safe." In some programs, even variables of type double will be inadequatesuch programs are beyond the scope of this book. Most programmers represent floating-point numbers with type double. In fact, C++ treats all floating-point numbers you type in a program's source code (such as 7.33 and 0.0975) as double values by default. Such values in the source code are known as floating-point constants. See Appendix C, Fundamental Types, for the ranges of values for floats and doubles.
Floating-point numbers often arise as a result of division. In conventional arithmetic, when we divide 10 by 3, the result is 3.3333333..., with the sequence of 3s repeating infinitely. The computer allocates only a fixed amount of space to hold such a value, so clearly the stored floating-point value can be only an approximation.
Common Programming Error 4.12
|
Using floating-point numbers in a manner that assumes they are represented exactly (e.g., using them in comparisons for equality) can lead to incorrect results. Floating-point numbers are represented only approximately by most computers. |
Although floating-point numbers are not always 100% precise, they have numerous applications. For example, when we speak of a "normal" body temperature of 98.6, we do not need to be precise to a large number of digits. When we read the temperature on a thermometer as 98.6, it may actually be 98.5999473210643. Calling this number simply 98.6 is fine for most applications involving body temperatures. Due to the imprecise nature of floating-point numbers, type double is preferred over type float, because double variables can represent floating-point numbers more accurately. For this reason, we use type double throughout the book.
Converting Between Fundamental Types Explicitly and Implicitly
The variable average is declared to be of type double (line 55 of Fig. 4.13) to capture the fractional result of our calculation. However, total and gradeCounter are both integer variables. Recall that dividing two integers results in integer division, in which any fractional part of the calculation is lost (i.e., truncated). In the following statement:
average = total / gradeCounter;
the division calculation is performed first, so the fractional part of the result is lost before it is assigned to average. To perform a floating-point calculation with integer values, we must create temporary values that are floating-point numbers for the calculation. C++ provides the unary cast operator to accomplish this task. Line 81 uses the cast operator static_cast< double >( total ) to create a temporary floating-point copy of its operand in parenthesestotal. Using a cast operator in this manner is called explicit conversion. The value stored in total is still an integer.
The calculation now consists of a floating-point value (the temporary double version of total) divided by the integer gradeCounter. The C++ compiler knows how to evaluate only expressions in which the data types of the operands are identical. To ensure that the operands are of the same type, the compiler performs an operation called promotion (also called implicit conversion) on selected operands. For example, in an expression containing values of data types int and double, C++ promotes int operands to double values. In our example, we are treating total as a double (by using the unary cast operator), so the compiler promotes gradeCounter to double, allowing the calculation to be performedthe result of the floating-point division is assigned to average. In Chapter 6, Functions and an Introduction to Recursion, we discuss all the fundamental data types and their order of promotion.
Common Programming Error 4.13
|
The cast operator can be used to convert between fundamental numeric types, such as int and double, and between related class types (as we discuss in Chapter 13, Object-Oriented Programming: Polymorphism). Casting to the wrong type may cause compilation errors or runtime errors. |
Cast operators are available for use with every data type and with class types as well. The static_cast operator is formed by following keyword static_cast with angle brackets (< and >) around a data type name. The cast operator is a unary operatoran operator that takes only one operand. In Chapter 2, we studied the binary arithmetic operators. C++ also supports unary versions of the plus (+) and minus (-) operators, so that the programmer can write such expressions as -7 or +5. Cast operators have higher precedence than other unary operators, such as unary + and unary -. This precedence is higher than that of the multiplicative operators *, / and %, and lower than that of parentheses. We indicate the cast operator with the notation static_cast< type >() in our precedence charts (see, for example, Fig. 4.22).
Formatting for Floating-Point Numbers
The formatting capabilities in Fig. 4.13 are discussed here briefly and explained in depth in Chapter 15, Stream Input/Output. The call to setprecision in line 86 (with an argument of 2) indicates that double variable average should be printed with two digits of precision to the right of the decimal point (e.g., 92.37). This call is referred to as a parameterized stream manipulator (because of the 2 in parentheses). Programs that use these calls must contain the preprocessor directive (line 10)
#include
Line 11 specifies the names from the header file that are used in this program. Note that endl is a nonparameterized stream manipulator (because it is not followed by a value or expression in parentheses) and does not require the header file. If the precision is not specified, floating-point values are normally output with six digits of precision (i.e., the default precision on most 32-bit systems today), although we will see an exception to this in a moment.
The stream manipulator fixed (line 86) indicates that floating-point values should be output in so-called 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 and 10, multiplied by a power of 10. For instance, the value 3,100 would be displayed in scientific notation as 3.1 x 103. Scientific notation is useful when displaying values that are very large or very small. Formatting using scientific notation is discussed further in Chapter 15. Fixed-point formatting, on the other hand, is used to force a floating-point number to display a specific number of digits. Specifying 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, such a value prints in C++ as 88 without the trailing zeros and without the decimal point. When the stream manipulators fixed and setprecision are used in a program, the printed value is rounded to the number of decimal positions indicated by the value passed to setprecision (e.g., the value 2 in line 86), 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. Note that it also is 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, stream manipulators fixed and showpoint are nonparameterized and do not require the header file. Both can be found in header .
Lines 86 and 87 of Fig. 4.13 output the class average. In this example, we display the class average rounded to the nearest hundredth and output it with exactly two digits to the right of the decimal point. The parameterized stream manipulator (line 86) indicates that variable average's value should be displayed with two digits of precision to the right of the decimal pointindicated by setprecision( 2 ). The three grades entered during the sample execution of the program in Fig. 4.14 total 257, which yields the average 85.666666.... The parameterized stream manipulator setprecision causes the value to be rounded to the specified number of digits. In this program, the average is rounded to the hundredths position and displayed as 85.67.