Section 4.9. Formulating Algorithms: Sentinel-Controlled Repetition


[Page 140 ( continued )]

4.9. Formulating Algorithms: Sentinel-Controlled Repetition

Let us generalize Section 4.8's class-average problem. Consider the following problem:

Develop a class-averaging program that processes grades for an arbitrary number of students each time it is run.

In the previous class-average example, the problem statement specified the number of students, so the number of grades (10) was known in advance. In this example, no indication is given of how many grades the user will enter during the program's execution. The program must process an arbitrary number of grades. How can it determine when to stop the input of grades? How will it know when to calculate and print 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." The user enters grades until all legitimate grades have been entered. The user then types the sentinel value to indicate that no more grades will be entered. Sentinel-controlled repetition is often called indefinite repetition because the number of repetitions is not known before the loop begins executing.

Clearly, a sentinel value must be chosen that cannot be confused with an acceptable input value. Grades on a quiz are nonnegative integers, so 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. Since 1 is the sentinel value, it should not enter into the averaging calculation.


[Page 141]

Common Programming Error 4.6

Choosing a sentinel value that is also a legitimate data value is a logic error.


Developing the Pseudocode Algorithm with Top-Down, Stepwise Refinement: The Top and First Refinement

We approach the class-average program with a technique called top-down, stepwise refinement , which is essential to the development of well-structured programs. We begin with a pseudocode representation of the top a single statement that conveys the overall function of the program:


       Determine the class average for the quiz

The top is, in effect, a complete representation of a program. Unfortunately, the top rarely conveys sufficient detail from which to write a Java program. So we now begin the refinement process. We divide the top into a series of smaller tasks and list these in the order in which they will be performed. This results in the following first refinement :


       Initialize variables
       Input, sum and count the quiz grades
       Calculate and print the class average

This refinement uses only the sequence structurethe steps listed should execute in order, one after the other.

Software Engineering Observation 4.2

Each refinement, as well as the top itself, is a complete specification of the algorithmonly the level of detail varies.


Software Engineering Observation 4.3

Many programs can be divided logically into three phases: an initialization phase that initializes the variables; a processing phase that inputs data values and adjusts program variables (e.g., counters and totals) accordingly ; and a termination phase that calculates and outputs the final results.


Proceeding to the Second Refinement

The preceding Software Engineering Observation is often all you need for the first refinement in the top-down process. To proceed to the next level of refinement, that is, the second refinement , we commit to specific variables. In this example, we need a running total of the numbers, a count of how many numbers have been processed , a variable to receive the value of each grade as it is input by the user and a variable to hold the calculated average. The pseudocode statement


       Initialize variables

can be refined as follows :


       Initialize total to zero
       Initialize counter to zero

Only the variables total and counter need to be initialized before they are used. The variables average and grade (for the calculated average and the user input, respectively) need not be initialized, because their values will be replaced as they are calculated or input.


[Page 142]

The pseudocode statement


       Input, sum and count the quiz grades

requires a repetition structure (i.e., a loop) that successively inputs each grade. We do not know in advance how many grades are to be processed, so we will use sentinel-controlled repetition. The user enters grades one at a time. After entering the last grade, the user enters the sentinel value. The program tests for the sentinel value after each grade is input and terminates the loop when the user enters the sentinel value. The second refinement of the preceding pseudocode statement is then


       Prompt the user to enter the first grade
       Input the first grade (possibly the sentinel)

       While the user has not yet entered the sentinel
           Add this grade into the running total
           Add one to the grade counter
           Prompt the user to enter the next grade
           Input the next grade (possibly the sentinel)

In pseudocode, we do not use braces around the statements that form the body of the While structure. We simply indent the statements under the While to show that they belong to the While . Again, pseudocode is only an informal program-development aid.

The pseudocode statement


       Calculate and print 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 counter
             Print the average
       else
             Print "No grades were entered"

We are careful here to test for the possibility of division by zeronormally a logic error that, if undetected, would cause the program to fail or produce invalid output. The complete second refinement of the pseudocode for the class-average problem is shown in Fig. 4.8.

Figure 4.8. Class-average problem pseudocode algorithm with sentinel-controlled repetition.
(This item is displayed on pages 142 - 143 in the print version)


 1   Initialize total to zero
 2   Initialize counter to zero
 3
 4   Prompt the user to enter the first grade
 5   Input the first grade (possibly the sentinel)
 6
 7   While the user has not yet entered the sentinel
 8        Add this grade into the running total
 9        Add one to the grade counter
10        Prompt the user to enter the next grade
11        Input the next grade (possibly the sentinel)
12
13   If the counter is not equal to zero
14         Set the average to the total divided by the counter
15         Print the average
16   else
17         Print "No grades were entered"

Error-Prevention Tip 4.2

When performing division by an expression whose value could be zero, explicitly test for this possibility and handle it appropriately in your program (e.g., by printing an error message) rather than allow the error to occur



[Page 143]

In Fig. 4.5 and Fig. 4.8, we included some completely blank lines and indentation in the pseudocode to make it more readable. The blank lines separate the pseudocode algorithms into their various phases and set off control statements, and the indentation emphasizes the bodies of the control statements.

The pseudocode algorithm in Fig. 4.8 solves the more general class-averaging problem. This algorithm was developed after only two refinements. Sometimes more refinements are necessary.

Software Engineering Observation 4.4

Terminate the top-down, stepwise refinement process when you have specified the pseudocode algorithm in sufficient detail for you to convert the pseudocode to Java. Normally, implementing the Java program is then straightforward.


Software Engineering Observation 4.5

Some experienced programmers write programs without ever using program-development tools like pseudocode. They feel that their ultimate goal is to solve the problem on a computer and that writing pseudocode merely delays the production of final outputs. Although this method may work for simple and familiar problems, it can lead to serious errors and delays in large, complex projects.


Implementing Sentinel-Controlled Repetition in Class GradeBook

Figure 4.9 shows the Java class GradeBook containing method determineClassAverage that implements the pseudocode algorithm of Fig. 4.8. Although each grade is an integer, the averaging calculation is likely to produce a number with a decimal pointin other words, a real number or floating-point number. The type int cannot represent such a number, so this class uses type double to do so.

Figure 4.9. Sentinel-controlled repetition: Class-average problem.
(This item is displayed on pages 143 - 145 in the print version)
1

// Fig. 4.9: GradeBook.java

2

// GradeBook class that solves class-average program using

3

// sentinel-controlled repetition.

4

import

java.util.Scanner;

// program uses class Scanner

5
 6

public class

GradeBook
 7  {
 8

private

String courseName;

// name of course this GradeBook represents

9
10

// constructor initializes courseName

11

public

GradeBook( String name )
12     {
13        courseName = name;

// initializes courseName

14     }

// end constructor

15
16

// method to set the course name

17

public void

setCourseName( String name )
18     {
19        courseName = name;

// store the course name

20     }

// end method setCourseName

21
22

// method to retrieve the course name

23

public

String getCourseName()
24     {
25

return

courseName;
26     }

// end method getCourseName

27
28

// display a welcome message to the GradeBook user

29

public void

displayMessage()
30     {
31

// getCourseName gets the name of the course

32        System.out.printf(

"Welcome to the grade book for\n%s!\n\n"

,
33           getCourseName() );
34     }

// end method displayMessage

35
36

// determine the average of an arbitrary number of grades

37


public void

determineClassAverage()

38     {
39

// create Scanner to obtain input from command window

40        Scanner input =

new

Scanner( System.in );
41
42

int

total;

// sum of grades

43

int

gradeCounter;

// number of grades entered

44

int

grade;

// grade value

45


double

average;

// number with decimal point for average


46
47

// initialization phase

48        total =


;

// initialize total

49

gradeCounter =


;

// initialize loop counter


50
51

// processing phase

52


// prompt for input and read grade from user


53

System.out.print(

"Enter grade or -1 to quit: "

);

54

grade = input.nextInt();

55
56


// loop until sentinel value read from user


57

while

( grade !=

-1

)
58        {
59           total = total + grade;

// add grade to total

60           gradeCounter = gradeCounter +

1

;

// increment counter

61 
62


// prompt for input and read next grade from user


63

System.out.print(

"Enter grade or -1 to quit: "

);

64

grade = input.nextInt();

65        }

// end while

66 
67

// termination phase

68

// if user entered at least one grade...

69

if

(

gradeCounter !=



)
70        {
71


// calculate average of all grades entered


72

average = (

double

) total / gradeCounter;

73 
74

// display total and average (with two digits of precision)

75           System.out.printf(

"\nTotal of the %d grades entered is %d\n"

,
76              gradeCounter, total );
77           System.out.printf(

"Class average is %.2f\n"

, average );
78        }

// end if

79

else


// no grades were entered, so output appropriate message

80           System.out.println(

"No grades were entered"

);
81     }

// end method determineClassAverage

82 
83  }

// end class GradeBook



[Page 145]

In this example, we see that control statements may be stacked on top of one another (in sequence) just as a child stacks building blocks. The while statement (lines 5765) is followed in sequence by an if ... else statement (lines 6980). Much of the code in this program is identical to the code in Fig. 4.6, so we concentrate on the new features and issues.

Line 45 declares double variable average. This variable allows us to store the calculated class average as a floating-point number. Line 49 initializes gradeCounter to , because no grades have been entered yet. Remember that this program uses sentinel-controlled repetition to input the grades from the user. To keep an accurate record of the number of grades entered, the program increments gradeCounter only when the user inputs a valid grade value.

Program Logic for Sentinel-Controlled Repetition vs. Counter-Controlled Repetition

Compare the program logic for sentinel-controlled repetition in this application with that for counter-controlled repetition in Fig. 4.6. In counter-controlled repetition, each iteration of the while statement (e.g., lines 5258 of Fig. 4.6) reads a value from the user, for the specified number of iterations. In sentinel-controlled repetition, the program reads the first value (lines 5354 of Fig. 4.9) before reaching the while . This value determines whether the program's flow of control should enter the body of the while . If the condition of the while is false, the user entered the sentinel value, so the body of the while does not execute (i.e., no grades were entered). If, on the other hand, the condition is true, the body begins execution, and the loop adds the grade value to the total (line 59). Then lines 6364 in the loop's body input the next value from the user. Next, program control reaches the closing right brace ( } ) of the body at line 65, so execution continues with the test of the while 's condition (line 57). The condition uses the most recent grade input by the user to determine whether the loop's body should execute again. Note that the value of variable grade is always input from the user immediately before the program tests the while condition. This allows the program to determine whether the value just input is the sentinel value before the program processes that value (i.e., adds it to the total ). If the sentinel value is input, the loop terminates, and the program does not add 1 to the total .


[Page 146]

Good Programming Practice 4.6

In a sentinel-controlled loop, the prompts requesting data entry should explicitly remind the user of the sentinel value.


After the loop terminates, the if ... else statement at lines 6980 executes. The condition at line 69 determines whether any grades were input. If none were input, the else part (lines 7980) of the if ... else statement executes and displays the message "No grades were entered" and the method returns control to the calling method.

Notice the while statement's block in Fig. 4.9 (lines 5865). Without the braces, the loop would consider its body to be only the first statement, which adds the grade to the total . The last three statements in the block would fall outside the loop's body, causing the computer to interpret the code incorrectly as follows:


while

( grade !=

-1

)
         total = total + grade;

// add grade to total

gradeCounter = gradeCounter +

1

;

// increment counter


// prompt for input and read next grade from user

System.out.print(

"Enter grade or -1 to quit: "

);
      grade = input.nextInt();


The preceding code would cause an infinite loop in the program if the user did not input the sentinel -1 at line 54 (before the while statement).

Common Programming Error 4.7

Omitting the braces that delimit a block can lead to logic errors, such as infinite loops . To prevent this problem, some programmers enclose the body of every control statement in braces even if the body contains only a single statement.


Explicitly and Implicitly Converting Between Primitive Types

If at least one grade was entered, line 72 of Fig. 4.9 calculates the average of the grades. Recall from Fig. 4.6 that integer division yields an integer result. Even though variable average is declared as a double (line 45), the calculation

average = total / gradeCounter;


loses the fractional part of the quotient before the result of the division is assigned to average . This occurs because total and gradeCounter are both integers and integer division yields an integer result. To perform a floating-point calculation with integer values, we must temporarily treat these values as floating-point numbers for use in the calculation. Java provides the unary cast operator to accomplish this task. Line 72 uses the (double) cast operatora unary operatorto create a temporary floating-point copy of its operand total (which appears to the right of the operator). Using a cast operator in this manner is called explicit conversion . The value stored in total is still an integer.


[Page 147]

The calculation now consists of a floating-point value (the temporary double version of total ) divided by the integer gradeCounter . Java knows how to evaluate only arithmetic expressions in which the operands' types are identical. To ensure that the operands are of the same type, Java performs an operation called promotion (or implicit conversion ) on selected operands. For example, in an expression containing values of the types int and double , the int values are promoted to double values for use in the expression. In this example, the value of gradeCounter is promoted to type double , then the floating-point division is performed and the result of the calculation is assigned to average . As long as the (double) cast operator is applied to any variable in the calculation, the calculation will yield a double result. Later in this chapter, we discuss all the primitive types. You will learn more about the promotion rules in Section 6.7.

Common Programming Error 4.8

The cast operator can be used to convert between primitive numeric types, such as int and double , and between related reference types (as we discuss in Chapter 10, Object-Oriented Programming: Polymorphism). Casting to the wrong type may cause compilation errors or runtime errors.


Cast operators are available for any type. The cast operator is formed by placing parentheses around the name of a type. The operator is a unary operator (i.e., an operator that takes only one operand). In Chapter 2, we studied the binary arithmetic operators. Java also supports unary versions of the plus ( + ) and minus ( - ) operators, so the programmer can write expressions like -7 or +5 . Cast operators associate from right to left and have the same precedence as other unary operators, such as unary + and unary - . This precedence is one level higher than that of the multiplicative operators * , / and % . (See the operator precedence chart in Appendix A.) We indicate the cast operator with the notation ( type ) in our precedence charts , to indicate that any type name can be used to form a cast operator.

Line 77 outputs the class average using System.out 's printf method. In this example, we decided that we'd like to display the class average rounded to the nearest hundredth and output the average with exactly two digits to the right of the decimal point. The format specifier %.2f in printf 's format control string (line 77) indicates that variable average 's value should be displayed with two digits of precision to the right of the decimal pointindicated by .2 in the format specifier. The three grades entered during the sample execution of class GradeBookTest (Fig. 4.10) total 257, which yields the average 85.666666....Method printf uses the precision in the format specifier to round the value to the specified number of digits. In this program, the average is rounded to the hundredths position and the average is displayed as 85.67 .

Figure 4.10. GradeBookTest class creates an object of class GradeBook (Fig. 4.9) and invokes its determineClassAverage method.
(This item is displayed on pages 147 - 148 in the print version)
1

// Fig. 4.10: GradeBookTest.java

2

// Create GradeBook object and invoke its determineClassAverage method.

3
 4

public class

GradeBookTest
 5  {
 6

public static void

main( String args[] )
 7     {
 8

// create GradeBook object myGradeBook and

9

// pass course name to constructor

10        GradeBook myGradeBook =

new

GradeBook(
11

"CS101 Introduction to Java Programming"

);
12
13        myGradeBook.displayMessage();

// display welcome message

14        myGradeBook.determineClassAverage();

// find average of grades

15     }

// end main

16
17  }

// end class GradeBookTest


Welcome to the grade book for
CS101 Introduction to Java Programming!

Enter grade or -1 to quit:

97

Enter grade or -1 to quit:

88

Enter grade or -1 to quit:

72

Enter grade or -1 to quit:

-1

Total of the 3 grades entered is 257
Class average is 85.67