5.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 10 students took a quiz. The grades (integers in the range 0 to 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.
5.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. 5.8) and a corresponding C# app (Fig. 5.9) that implements the algorithm. In Section 5.10, we demonstrate how to develop pseudo-code algorithms from scratch.
Fig. 5.8 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 10
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 10
11 Display the class average
Note the mentions in the algorithm of Fig. 5.8 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 5.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.
5.9.2 Implementing Counter-Controlled Iteration
In Fig. 5.9, method Main implements the class-averaging algorithm described by the pseudocode in Fig. 5.8—it allows the user to enter 10 grades, then calculates and displays the average.
Fig. 5.9 Solving the class-average problem using counter-controlled iteration.
Alternate View
1 // Fig. 5.9: ClassAverage.cs
2 // Solving the class-average problem using counter-controlled iteration.
3 using System;
4
5 class ClassAverage
6 {
7 static void Main()
8 {
9 // initialization phase
10 int total = 0; // initialize sum of grades entered by the user
11 int gradeCounter = 1; // initialize grade # to be entered next
12
13 // processing phase uses counter-controlled iteration
14 while (gradeCounter <= 10) // loop 10 times
15 {
16 Console.Write("Enter grade: "); // prompt
17 int grade = int.Parse(Console.ReadLine()); // input grade
18 total = total + grade; // add the grade to total
19 gradeCounter = gradeCounter + 1; // increment the counter by 1
20 }
21
22 // termination phase
23 int average = total / 10; // integer division yields integer result
24
25 // display total and average of grades
26 Console.WriteLine($"
Total of all 10 grades is {total}");
27 Console.WriteLine($"Class average is {average}");
28 }
29 }
Enter grade: 88 Enter grade: 79 Enter grade: 95 Enter grade: 100 Enter grade: 48 Enter grade: 88 Enter grade: 92 Enter grade: 83 Enter grade: 90 Enter grade: 85 Total of all 10 grades is 848 Class average is 84
Local Variables in Main
Lines 10, 11, 17 and 23 declare local variables total, gradeCounter, grade and average, respectively. A variable declared in a method 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
C# requires local variables to be definitely assigned—that is, each local variable must be assigned a value before the variable’s value is used. Lines 10–11 declare and initialize total to 0 and gradeCounter to 1 before their values are used, so these variables are definitely assigned (as are grade and average in lines 17 and 23, respectively).
Common Programming Error 5.3
All local variables must be definitely assigned before their values are used in expressions. Using a local variable’s value before it’s definitely assigned results in a compilation error.
Initializing local variables when they’re declared helps you avoid compilation errors that might arise from attempts to use uninitialized data. While C# does not require that local-variable initializations be incorporated into declarations, it does require that local variables be initialized before their values are used in an expression.
Error-Prevention Tip 5.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’re used (we’ll show examples of each). Error-Prevention Tip 5.3
Processing Phase: Reading 10 Grades from the User
Line 14 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 15–20).
Line 16 displays the prompt "Enter grade: ". Line 17 inputs the grade entered by the user and assigns it to variable grade. Then line 18 adds the new grade entered by the user to the total and assigns the result to total, replacing its previous value.
Line 19 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 14) becomes false.
Termination Phase: Calculating and Displaying the Class Average
When the loop terminates, line 23 performs the averaging calculation in the average variable’s initializer. Line 26 displays the text "Total of all 10 grades is " followed by variable total’s value. Then, line 27 displays the text "Class average is " followed by variable average’s value. When execution reaches line 28, the program terminates.
Notice that this example contains only one class, with method Main performing all the work. In this chapter and in Chapter 3, you’ve seen examples consisting of two classes:
one containing instance variables, properties and methods that perform tasks using the instance variables and properties, and
one containing method
Main, which creates an object of the other class and calls its methods and accesses its properties.
Occasionally, when it does not make sense to create a separate class to demonstrate a concept, we’ll place the program’s statements entirely within a single class’s Main method.
5.9.3 Integer Division and Truncation
The averaging calculation performed in line 23 produces an integer result. The app’s output indicates that the sum of the grade values in the sample execution is 848, which, when divided by 10, should yield 84.8. However, the result of the calculation total / 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 lost (i.e., truncated, not rounded). We’ll see how to obtain a floating-point result from the averaging calculation in the next section.
Common Programming Error 5.4
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.