4.9 Formulating Algorithms: Counter-Controlled Iteration
To illustrate how algorithms are developed, we solve two variations of a problem that averages student grades. Consider the following problem statement:
A class of ten students took a quiz. The grades (integers in the range 0–100) for this quiz are available to you. Determine the class average on the quiz.
The class average is equal to the sum of the grades divided by the number of students. The algorithm for solving this problem on a computer must input each grade, keep track of the total of all grades entered, perform the averaging calculation and print the result.
4.9.1 Pseudocode Algorithm with Counter-Controlled Iteration
Let’s use pseudocode to list the actions to execute and specify the order in which they should execute. We use counter-controlled iteration to input the grades one at a time. This technique uses a variable called a counter (or control variable) to control the number of times a set of statements will execute. Counter-controlled iteration is often called definite iteration, because the number of iterations is known before the loop begins executing. In this example, iteration terminates when the counter exceeds 10. This section presents a fully developed pseudocode algorithm (Fig. 4.9) and a corresponding C++ program (Fig. 4.10) that implements the algorithm. In Section 4.10, we demonstrate how to develop pseudocode algorithms from scratch.
Fig. 4.9 Pseudocode algorithm that uses counter-controlled iteration to solve the class-average problem.
Alternate View
1 Set total to zero
2 Set grade counter to one
3
4 While grade counter is less than or equal to ten
5 Prompt the user to enter the next grade
6 Input the next grade
7 Add the grade into the total
8 Add one to the grade counter
9
10 Set the class average to the total divided by ten
11 Print the class average
Note the references in the algorithm of Fig. 4.9 to a total and a counter. A total is a variable used to accumulate the sum of several values. A counter is a variable used to count—in this case, the grade counter indicates which of the 10 grades is about to be entered by the user. Variables used to store totals normally are initialized to zero before being used in a program. In pseudocode, we do not use braces around the statements that form the body of the pseudocode While structure, but you could.
Software Engineering Observation 4.1
Experience has shown that the most difficult part of solving a problem on a computer is developing the algorithm for the solution. Once a correct algorithm has been specified, producing a working C++ program from it is usually straightforward.
4.9.2 Implementing Counter-Controlled Iteration
In Fig. 4.10, the main function implements the class-averaging algorithm described by the pseudocode in Fig. 4.9—it allows the user to enter 10 grades, then calculates and displays the average.
Fig. 4.10 Solving the class-average problem using counter-controlled iteration.
Alternate View
1 // Fig. 4.10: ClassAverage.cpp
2 // Solving the class-average problem using counter-controlled iteration.
3 #include <iostream>
4 using namespace std;
5
6 int main() {
7 // initialization phase
8 int total{0}; // initialize sum of grades entered by the user
9 unsigned int gradeCounter{1}; // initialize grade # to be entered next
10
11 // processing phase uses counter-controlled iteration
12 while (gradeCounter <= 10) { // loop 10 times
13 cout << "Enter grade: "; // prompt
14 int grade;
15 cin >> grade; // input next grade
16 total = total + grade; // add grade to total
17 gradeCounter = gradeCounter + 1; // increment counter by 1
18 }
19
20 // termination phase
21 int average{total / 10}; // int division yields int result
22
23 // display total and average of grades
24 cout << "
Total of all 10 grades is " << total;
25 cout << "
Class average is " << average << endl;
26 }
Enter grade: 67 Enter grade: 78 Enter grade: 89 Enter grade: 67 Enter grade: 87 Enter grade: 98 Enter grade: 93 Enter grade: 85 Enter grade: 82 Enter grade: 100 Total of all 10 grades is 846 Class average is 84
Local Variables in main
Lines 8, 9, 14 and 21 declare local variables total, gradeCounter, grade and average, respectively. Variable gradeCounter is of type unsigned int, because it can assume only the values from 1 through 11 (11 terminates the loop), which are all positive values. In general, counters that should store only nonnegative values should be declared with unsigned types. Variables of unsigned integer types can represent values from 0 to approximately twice the positive range of the corresponding signed integer types. You can determine your platform’s maximum unsigned int value with the constant UINT_MAX from <climits>. The program’s other variables are of type int. Variable grade stores the user input.
A variable declared in a function body is a local variable and can be used only from the line of its declaration to the closing right brace of the block in which the variable is declared. A local variable’s declaration must appear before the variable is used; otherwise, a compilation error occurs. Variable grade—declared in the body of the while loop—can be used only in that block.
Initialization Phase: Initializing Variables total and gradeCounter
Lines 8–9 declare and initialize total to 0 and gradeCounter to 1. These initializations occur before the variables are used in calculations.
Error-Prevention Tip 4.2
Initialize each total and counter, either in its declaration or in an assignment statement. Totals are normally initialized to 0. Counters are normally initialized to 0 or 1, depending on how they’re used (we’ll show examples of when to use 0 and when to use 1).
Processing Phase: Reading 10 Grades from the User
Line 12 indicates that the while statement should continue looping (also called iterating) as long as gradeCounter’s value is less than or equal to 10. While this condition remains true, the while statement repeatedly executes the statements between the braces that delimit its body (lines 12–18).
Line 13 displays the prompt "Enter grade: ". Line 15 inputs the grade entered by the user and assigns it to variable grade. Then line 16 adds the new grade entered by the user to the total and assigns the result to total, replacing its previous value.
Line 17 adds 1 to gradeCounter to indicate that the program has processed a grade and is ready to input the next grade from the user. Incrementing gradeCounter eventually causes it to exceed 10. Then the loop terminates, because its condition (line 12) becomes false.
Termination Phase: Calculating and Displaying the Class Average
When the loop terminates, line 21 performs the averaging calculation in the average variable’s initializer. Line 24 displays the text "Total of all 10 grades is " followed by variable total’s value. Then, line 25 displays the text "Class average is " followed by variable average’s value. When execution reaches line 26, the program terminates.
Notice that this example contains only a main function that performs all the work. In this chapter and in Chapter 3, you’ve seen examples consisting of a class and a main program that creates an object of the class and calls its member functions. When it does not make sense to try to create a reusable class to demonstrate a concept, we’ll place the program’s statements entirely within main.
4.9.3 Notes on Integer Division and Truncation
This example’s averaging calculation produces an integer result. The program’s output indicates that the sum of the grade values in the sample execution is 846, which, when divided by 10, should yield the floating-point number 84.6. However, the result of the calculation total / 10 (line 21 of Fig. 4.10) is the integer 84, because total and 10 are both integers. Dividing two integers results in integer division—any fractional part of the calculation is truncated (i.e., lost). In the next section we’ll see how to obtain a floating-point result from the averaging calculation.
Common Programming Error 4.3
Assuming that integer division rounds (rather than truncates) can lead to incorrect results. For example, 7 ÷ 4, which yields 1.75 in conventional arithmetic, truncates to 1 in integer arithmetic, rather than rounding to 2.
4.9.4 Arithmetic Overflow
In Fig. 4.10, line 16
total = total + grade; // add grade to total
adds each grade entered by the user to the total. Even this simple statement has a potential problem—adding the integers could result in a value that’s too large to store in an int variable. This is known as arithmetic overflow and causes undefined behavior, which can lead to unintended results and security problems. See, for example,
http://en.wikipedia.org/wiki/Integer_overflow#Security_ramifications
Figure 2.5 had the same issue in line 19, which calculated the sum of two int values entered by the user:
sum = number1 + number2; // add the numbers; store result in sum
The maximum and minimum values that can be stored in an int variable are represented by the constants INT_MAX and INT_MIN, respectively, which are defined in the header <climits>. There are similar constants for the other integral types and for floating-point types (header <cfloat>). To see these constants’ values on your platform, include the appropriate header in a program that outputs the values with cout, as in
cout << "INT_MAX = " << INT_MAX << "
";
For arithmetic calculations like those in line 16 of Fig. 4.10 and line 19 of Fig. 2.5, it’s considered a good practice to ensure before you perform them that they will not overflow. The code for doing this is shown at www.securecoding.cert.org—just search for guideline “INT32-CPP.” The code uses the && (logical AND) and || (logical OR) operators, which are introduced in Chapter 5.
4.9.5 Input Validation
Any time a program receives input from the user, various problems might occur. For example, in line 15 of Fig. 4.10
cin >> grade; // input next grade
we assume that the user will enter an integer grade in the range 0 to 100. However, the user could enter an integer less than 0, an integer greater than 100, an integer outside the range of values that can be stored in an int variable, a number containing a decimal point or a value containing letters or special symbols that’s not even an integer.
To ensure that inputs are valid, industrial-strength programs must test for all possible erroneous cases. A program that inputs grades should validate the grades by using range checking to ensure that they’re values from 0 to 100. You can then ask the user to reenter any value that’s out of range. If a program requires inputs from a specific set of values (e.g., nonsequential product codes), you can ensure that each input matches a value in the set.