Formulating Algorithms: Counter-Controlled Repetition
Formulating Algorithms Counter Controlled Repetition
To illustrate how programmers develop algorithms, this section and Section 4.9 solve two variations of a class average problem. Consider the following problem statement:
A class of ten students took a quiz. The grades (integers in the range 0 to 100) for this quiz are available to you. Calculate and display the total of all student grades and 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 of the grades, calculate the average and print the result.
Pseudocode Algorithm with Counter-Controlled Repetition
Let's use pseudocode to list the actions to execute and specify the order in which these actions should occur. We use counter-controlled repetition to input the grades one at a time. This technique uses a variable called a counter to control the number of times a group of statements will execute (also known as the number of iterations of the loop).
Counter-controlled repetition is often called definite repetition because the number of repetitions is known before the loop begins executing. In this example, repetition terminates when the counter exceeds 10. This section presents a fully developed pseudocode algorithm (Fig. 4.7) and a version of class GradeBook (Fig. 4.8Fig. 4.9) that implements the algorithm in a C++ member function. The section then presents an application (Fig. 4.10) that demonstrates the algorithm in action. In Section 4.9 we demonstrate how to use pseudocode to develop such an algorithm from scratch.
|
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 total of the grades for all students in the class 12 Print the class average |
Figure 4.8. Class average problem using counter-controlled repetition: GradeBook header file.
(This item is displayed on page 140 in the print version)
|
1 // Fig. 4.8: 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.9. Class average problem using counter-controlled repetition: GradeBook source code file.
(This item is displayed on pages 141 - 142 in the print version)
|
1 // Fig. 4.9: GradeBook.cpp 2 // Member-function definitions for class GradeBook that solves the 3 // class average program with counter-controlled repetition. 4 #include 5 using std::cout; 6 using std::cin; 7 using std::endl; 8 9 #include "GradeBook.h" // include definition of class GradeBook 10 11 // constructor initializes courseName with string supplied as argument 12 GradeBook::GradeBook( string name ) 13 { 14 setCourseName( name ); // validate and store courseName 15 } // end GradeBook constructor 16 17 // function to set the course name; 18 // ensures that the course name has at most 25 characters 19 void GradeBook::setCourseName( string name ) 20 { 21 if ( name.length() <= 25 ) // if name has 25 or fewer characters 22 courseName = name; // store the course name in the object 23 else // if name is longer than 25 characters 24 { // set courseName to first 25 characters of parameter name 25 courseName = name.substr( 0, 25 ); // select first 25 characters 26 cout << "Name "" << name << "" exceeds maximum length (25). " 27 << "Limiting courseName to first 25 characters. " << endl; 28 } // end if...else 29 } // end function setCourseName 30 31 // function to retrieve the course name 32 string GradeBook::getCourseName() 33 { 34 return courseName; 35 } // end function getCourseName 36 37 // display a welcome message to the GradeBook user 38 void GradeBook::displayMessage() 39 { 40 cout << "Welcome to the grade book for " << getCourseName() << "! " 41 << endl; 42 } // end function displayMessage 43 44 // determine class average based on 10 grades entered by user 45 void GradeBook::determineClassAverage() 46 { 47 int total; // sum of grades entered by user 48 int gradeCounter; // number of the grade to be entered next 49 int grade; // grade value entered by user 50 int average; // average of grades 51 52 // initialization phase 53 total = 0; // initialize total 54 gradeCounter = 1; // initialize loop counter 55 56 // processing phase 57 while ( gradeCounter <= 10 ) // loop 10 times 58 { 59 cout << "Enter grade: "; // prompt for input 60 cin >> grade; // input next grade 61 total = total + grade; // add grade to total 62 gradeCounter = gradeCounter + 1; // increment counter by 1 63 } // end while 64 65 // termination phase 66 average = total / 10; // integer division yields integer result 67 68 // display total and average of grades 69 cout << " Total of all 10 grades is " << total << endl; 70 cout << "Class average is " << average << endl; 71 } // end function determineClassAverage |
Software Engineering Observation 4.3
|
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, the process of producing a working C++ program from the algorithm is normally straightforward. |
Note the references in the pseudocode algorithm of Fig. 4.7 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 countin this case, the grade counter indicates which of the 10 grades is about to be entered by the user. Variables used to store totals are normally initialized to zero before being used in a program; otherwise, the sum would include the previous value stored in the total's memory location.
Enhancing GradeBook Validation
Before we discuss the implementation of the class average algorithm, let's consider an enhancement we made to our GradeBook class. In Fig. 3.16, our setCourseName member function would validate the course name by first testing if the course name's length was less than or equal to 25 characters, using an if statement. If this was true, the course name would be set. This code was then followed by another if statement that tested if the course name's length was larger than 25 characters (in which case the course name would be shortened). Notice that the second if statement's condition is the exact opposite of the first if statement's condition. If one condition evaluates to true, the other must evaluate to false. Such a situation is ideal for an if...else statement, so we have modified our code, replacing the two if statements with one if...else statement (lines 2128 of Fig. 4.9).
Implementing Counter-Controlled Repetition in Class GradeBook
Class GradeBook (Fig. 4.8Fig. 4.9) contains a constructor (declared in line 11 of Fig. 4.8 and defined in lines 1215 of Fig. 4.9) that assigns a value to the class's instance variable courseName (declared in line 17 of Fig. 4.8). Lines 1929, 3235 and 3842 of Fig. 4.9 define member functions setCourseName, getCourseName and displayMessage, respectively. Lines 4571 define member function determineClassAverage, which implements the class average algorithm described by the pseudocode in Fig. 4.7.
Lines 4750 declare local variables total, gradeCounter, grade and average to be of type int. Variable grade stores the user input. Notice that the preceding declarations appear in the body of member function determineClassAverage.
In this chapter's versions of class GradeBook, we simply read and process a set of grades. The averaging calculation is performed in member function determineClassAverage using local variableswe do not preserve any information about student grades in the class's instance variables. In Chapter 7, Arrays and Vectors, we modify class GradeBook to maintain the grades in memory using an instance variable that refers to a data structure known as an array. This allows a GradeBook object to perform various calculations on the same set of grades without requiring the user to enter the grades multiple times.
Good Programming Practice 4.5
|
Separate declarations from other statements in functions with a blank line for readability. |
Lines 5354 initialize total to 0 and gradeCounter to 1. Note that variables total and gradeCounter are initialized before they are used in a calculation. Counter variables normally are initialized to zero or one, depending on their use (we will present examples showing each possibility). An uninitialized variable contains a "garbage" value (also called an undefined value)the value last stored in the memory location reserved for that variable. Variables grade and average (for the user input and calculated average, respectively) need not be initialized heretheir values will be assigned as they are input or calculated later in the function.
Common Programming Error 4.6
|
Not initializing counters and totals can lead to logic errors. |
Error-Prevention Tip 4.2
|
Initialize each counter and total, 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 are used (we will show examples of when to use 0 and when to use 1). |
Good Programming Practice 4.6
|
Declare each variable on a separate line with its own comment to make programs more readable. |
Line 57 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 5863).
Line 59 displays the prompt "Enter grade: ". This line corresponds to the pseudocode statement "Prompt the user to enter the next grade." Line 60 reads the grade entered by the user and assigns it to variable grade. This line corresponds to the pseudocode statement "Input the next grade." Recall that variable grade was not initialized earlier in the program, because the program obtains the value for grade from the user during each iteration of the loop. Line 61 adds the new grade entered by the user to the total and assigns the result to total, which replaces its previous value.
Line 62 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 gradeCounter to exceed 10. At that point the while loop terminates because its condition (line 57) becomes false.
When the loop terminates, line 66 performs the averaging calculation and assigns its result to the variable average. Line 69 displays the text "Total of all 10 grades is " followed by variable total's value. Line 70 then displays the text "Class average is " followed by variable average's value. Member function determineClassAverage, then returns control to the calling function (i.e., main in Fig. 4.10).
Figure 4.10. Class average problem using counter-controlled repetition: Creating an object of class GradeBook (Fig. 4.8Fig. 4.9) and invoking its determineClassAverage member function.
(This item is displayed on page 143 in the print version)
|
1 // Fig. 4.10: fig04_10.cpp 2 // Create GradeBook object and invoke its determineClassAverage function. 3 #include "GradeBook.h" // include definition of class GradeBook 4 5 int main() 6 { 7 // create GradeBook object myGradeBook and 8 // pass course name to constructor 9 GradeBook myGradeBook( "CS101 C++ Programming" ); 10 11 myGradeBook.displayMessage(); // display welcome message 12 myGradeBook.determineClassAverage(); // find average of 10 grades 13 return 0; // indicate successful termination 14 } // end main
|
Demonstrating Class GradeBook
Figure 4.10 contains this application's main function, which creates an object of class GradeBook and demonstrates its capabilities. Line 9 of Fig. 4.10 creates a new GradeBook object called myGradeBook. The string in line 9 is passed to the GradeBook constructor (lines 1215 of Fig. 4.9). Line 11 of Fig. 4.10 calls myGradeBook's displayMessage member function to display a welcome message to the user. Line 12 then calls myGradeBook's determineClassAverage member function to allow the user to enter 10 grades, for which the member function then calculates and prints the averagethe member function performs the algorithm shown in the pseudocode of Fig. 4.7.
Notes on Integer Division and Truncation
The averaging calculation performed by member function determineClassAverage in response to the function call at line 12 in Fig. 4.10 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 84.6a number with a decimal point. However, the result of the calculation total / 10 (line 66 of Fig. 4.9) is the integer 84, because total and 10 are both integers. Dividing two integers results in integer divisionany fractional part of the calculation is lost (i.e., truncated). We will see how to obtain a result that includes a decimal point from the averaging calculation in the next section.
Common Programming Error 4.7
|
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. |
In Fig. 4.9, if line 66 used gradeCounter rather than 10 for the calculation, the output for this program would display an incorrect value, 76. This occurs because in the final iteration of the while statement, gradeCounter was incremented to the value 11 in line 62.
Common Programming Error 4.8
|
Using a loop's counter-control variable in a calculation after the loop often causes a common logic error called an off-by-one-error. In a counter-controlled loop that counts up by one each time through the loop, the loop terminates when the counter's value is one higher than its last legitimate value (i.e., 11 in the case of counting from 1 to 10). |