3.11 Program Development: Sentinel-Controlled Repetition
Let’s generalize the class-average problem. Consider the following requirements statement:
-
Develop a class-averaging program that processes an arbitrary number of grades each time the program executes.
In the first class-average example, we knew in advance the 10 grades to process. The requirements statement does not state what the grades are or how many there are, so we’re going to have the user enter the grades into the program. The program processes an arbitrary number of grades. How can the program determine when to stop processing grades so that it can move on to calculate and display 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.” This is a bit like the way a caboose “marks” the end of a train. The user enters grades one at a time until all the grades have been entered. The user then enters the sentinel value to indicate that there are no more grades. Sentinel-controlled repetition is often called indefinite repetition because the number of repetitions is not known before the loop begins executing.
A sentinel value must not be confused with any acceptable input value. Grades on a quiz are typically nonnegative integers between 0 and 100, so the value –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. The sentinel value –1 should not enter into the averaging calculation.
Developing the Pseudocode Algorithm with Top-Down, Stepwise Refinement
We approach this class-average problem with a technique called top-down, stepwise refinement. We begin with a pseudocode representation of the top:
Determine the class average for the quiz
The top is a single statement that conveys the program’s overall function. Although it’s a complete representation of a program, the top rarely conveys enough detail from which to write a program. The top specifies what should be done, but not how to implement it. So we begin the refinement process. We decompose the top into a sequence of smaller tasks—a process sometimes called divide and conquer. This results in the following first refinement:
Initialize variables
Input, sum and count the quiz grades
Calculate and display the class average
Each refinement represents the complete algorithm—only the level of detail varies. In this refinement, the three pseudocode statements happen to correspond to the three execution phases described in the preceding section. The algorithm does not yet provide enough detail for us to write the Python program. So, we continue with the next refinement.
Second Refinement
To proceed to the second refinement, we commit to specific variables. The program needs to maintain
a grade variable in which each successive user input will be stored,
a running total of the grades,
a count of how many grades have been processed and
a variable that contains the calculated average.
The pseudocode statement
Initialize variables
can be refined as follows:
Initialize total to zero
Initialize grade counter to zero
Only the variables total and grade counter need to be initialized before they’re used. We do not initialize the variables for the user input and calculated average. Their values will be replaced each time we input a grade from the user and when we calculate the class average, respectively. We’ll create these variables when they’re needed.
The next pseudocode statement requires a loop that successively inputs each grade:
Input, sum and count the quiz grades
We do not know how many grades will be entered, so we use sentinel-controlled repetition. The user enters legitimate grades successively. After the last legitimate grade has been entered, the user enters the sentinel value. The program tests for the sentinel value after each grade is input and terminates the loop when the sentinel has been entered. The second refinement of the preceding pseudocode statement is
Input the first grade (possibly the sentinel)
While the user has not entered the sentinel
Add this grade into the running total
Add one to the grade counter
Input the next grade (possibly the sentinel)
The pseudocode statement
Calculate and display 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 grade counter
Display the average
Else
Display “No grades were entered”
Notice that we’re testing for the possibility of division by zero. If undetected, this would cause a fatal logic error. In the “Files and Exceptions” chapter, we discuss how to write programs that recognize such exceptions and take appropriate actions.
The following is the class-average problem’s complete second refinement:
Initialize total to zero
Initialize grade counter to zero
Input the first grade (possibly the sentinel)
While the user has not entered the sentinel
Add this grade into the running total
Add one to the grade counter
Input the next grade (possibly the sentinel)
If the counter is not equal to zero
Set the average to the total divided by the counter
Display the average
Else
Display “No grades were entered”
Sometimes more than two refinements are necessary. You stop refining when there is enough detail for you to convert the pseudocode to Python. We include blank lines for readability. Here, they happen to separate the algorithm into the three popular execution phases.
Implementing Sentinel-Controlled Iteration
The following script implements the pseudocode algorithm and shows a sample execution in which the user enters three grades and the sentinel value.
Fig. 3.2 | Class average program with sentinel-controlled iteration.
1 # fig03_02.py 2 """Class average program with sentinel-controlled iteration.""" 3 4 # initialization phase 5 total = 0 # sum of grades 6 grade_counter = 0 # number of grades entered 7 8 # processing phase 9 grade = int(input('Enter grade, -1 to end: ')) # get one grade 10 11 while grade != -1: 12 total += grade 13 grade_counter += 1 14 grade = int(input('Enter grade, -1 to end: ')) 15 16 # termination phase 17 if grade_counter != 0: 18 average = total / grade_counter 19 print(f'Class average is {average:.2f}') 20 else: 21 print('No grades were entered')
Enter grade, -1 to end: 97 Enter grade, -1 to end: 88 Enter grade, -1 to end: 72 Enter grade, -1 to end: -1 Class average is 85.67
Program Logic for Sentinel-Controlled Repetition
In sentinel-controlled repetition, the program reads the first value (line 9) before reaching the while statement. Line 9 demonstrates why we did not create the variable grade until we needed it in the program. If we had initialized it, that value would have been replaced immediately by this assignment.
The value input in line 9 determines whether the program’s flow of control should enter the while’s suite (lines 12–14). If the condition in line 11 is False, the user entered the sentinel value (-1), so the suite does not execute because the user did not enter any grades. If the condition is True, the suite executes, adding the grade value to the total and incrementing the grade_counter. Next, line 14 inputs another grade from the user. Then, the while’s condition (line 11) is tested again, using the most recent grade entered by the user. The value of grade is always input immediately before the program tests the while condition, so we can determine whether the value just input is the sentinel before processing that value as a grade. When the sentinel value is input, the loop terminates, and the program does not add –1 to the total. In a sentinel-controlled loop that performs user input, any prompts (lines 9 and 14) should remind the user of the sentinel value.
After the loop terminates, the if…else statement (lines 17–21) executes. Line 17 determines whether the user entered any grades. If not, the else part (lines 20–21) executes and displays the message 'No grades were entered' and the program terminates.
Formatting the Class Average with Two Decimal Places
This example formatted the class average with two digits to the right of the decimal point. In an f-string, you can optionally follow a replacement-text expression with a colon (:) and a format specifier that describes how to format the replacement text. The format specifier .2f (line 19) formats the average as a floating-point number (f) with two digits to the right of the decimal point (.2). In this example, the sum of the grades was 257, which, when divided by 3, yields 85.666666666…. Formatting the average with .2f rounds it to the hundredths position, producing the replacement text 85.67. An average with only one digit to the right of the decimal point would be formatted with a trailing zero (e.g., 85.50). The chapter “Strings: A Deeper Look” discusses many string-formatting features.
Control-Statement Stacking
In this example, notice that control statements are stacked in sequence. The while statement (lines 11–14) is followed immediately by an if…else statement (lines 17–21).
Self Check
(Fill-In) Sentinel-controlled repetition is called ___________ because the number of repetitions is not known before the loop begins executing.
Answer: indefinite repetition.(True/False) Sentinel-controlled repetition uses a counter variable to control the number of times a set of instructions executes.
Answer: False. Sentinel-control repetition terminates repetition when the sentinel value is encountered.