Formulating Algorithms Case Study CounterControlled Repetition
To illustrate how algorithms are developed, we solve several variations of a class-averaging problem. Consider the following problem statement:
A class often students took a quiz. The grades (integers in the range 0 -100) for this quiz are available. 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 requests each of the grades, performs the averaging calculation and prints the result.
Using pseudocode, we list the actions to be executed and specify the order in which these actions should be executed. 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 set of statements executes. Repetition terminates when the counter exceeds 10. In this section, we present a pseudocode algorithm (Fig. 3.9) and the corresponding program (Fig. 3.10). In the next section, we show how to develop pseudocode algorithms. Counter-controlled repetition often is called definite repetition because the number of repetitions is known before the loop begins executing.
Note the references in the algorithm to the variables total and counter. In the program of Fig. 3.10, the variable total (line 5) accumulates the sum of a series of values, while the variable counter counts—in this case, it counts the number of user-entered grades. Variables that store totals normally are initialized to zero.
Set total to zero
Set grade counter to one
While grade counter is less than or equal to ten Input the next grade Add the grade into the total Add one to the grade counter
Set the class average to the total divided by ten Print the class average
Fig. 3.9 Pseudocode algorithm that uses counter-controlled repetition to solve the class-average problem.
82 Control Structures
10 11 12
16 17
# Class average program with counter-controlled repetition.
# initialization phase total = 0 # sum of grades gradeCounter = 1 # number of grades entered
# processing phase while gradeCounter <= 10:
grade = raw_input( "Enter grade: grade = int( grade ) total = total + grade gradeCounter = gradeCounter + 1
# loop 10 times ) # get one grade # convert string to an integer
# termination phase average = total / 10 # integer division print "Class average is", average
# termination phase average = total / 10 # integer division print "Class average is", average
|
Enter |
grade: |
98 |
|
Enter |
grade: |
76 |
|
Enter |
grade: |
71 |
|
Enter |
grade: |
87 |
|
Enter |
grade: |
83 |
|
Enter |
grade: |
90 |
|
Enter |
grade: |
57 |
|
Enter |
grade: |
79 |
|
Enter |
grade: |
82 |
|
Enter |
grade: |
94 |
|
Class |
average is 81 | |
Fig. 3.10 Counter-controlled repetition used to solve class-average problem. Good Programming Practice 3.3
Initialize counters and totals.
Lines 5-6 are assignment statements that initialize total to 0 and gradeCounter to 1. Line 9 indicates that the while structure should continue as long as grade-Counter's value is less than or equal to 10.
Lines 10-11 correspond to the pseudocode statement Input the next grade. Function raw_input displays the prompt "Enter grade:" on the screen and accepts user input. Line 11 converts the user-entered string to an integer.
Next, the program updates total with the new grade entered by the user—line 12 adds grade to the previous value of total and assigns the result to total.
Then, the program increments the variable gradeCounter to indicate that a grade has been processed. Line 13 increments gradeCounter by one, allowing the condition in the while structure to evaluate to false and terminate the loop.
Line 16 executes after the while structure terminates and assigns the results of the average calculation to variable average. Line 17 displays the string "Class average is", followed by a space (inserted by print), followed by the value of variable average.
Chapter 3
Note that the averaging calculation in the program produces an integer result. Actually, the sum of the grades in this example is 817, which, when divided by 10, yields 81.7—a number with a decimal point. We discuss how to deal with floating-point numbers in the next section.
In Fig. 3.10, if line 16 used gradeCounter rather than 10 for the calculation, the output for this program would display an incorrect value, 74, because gradeCounter contains the values 11, after the termination of the while loop. Fig. 3.11 uses an interactive session to demonstrate the value of gradeCounter after the while loop iterates ten times.
Post a comment