Home | | Internet & World Wide Web HOW TO PROGRAM | | Internet Programming | | Web Programming | Formulating Algorithms: Sentinel-Controlled Repetition - JavaScript(JS)

# Formulating Algorithms: Sentinel-Controlled Repetition - JavaScript(JS)

Let us generalize the class-average problem. Consider the following problem:

Formulating Algorithms: Sentinel-Controlled Repetition

Let us generalize the class-average problem. Consider the following problem:

Develop a class-averaging program that will process an arbitrary number of grades each time the program is run.

In the first class-average example, the number of grades (10) was known in advance. In this example, no indication is given of how many grades the user will enter. The program must process an arbitrary number of grades. How can the program determine when to stop the input of grades? How will it know when 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 the end of data entry. The user types in grades until all legitimate grades have been entered. Then the user types the sentinel value to indicate that the last grade has been entered. Sentinel-controlled repeti-tion is often called indefinite repetition, because the number of repetitions is not known before the loop begins executing.

Clearly, one must choose a sentinel value that cannot be confused with an acceptable input value. –1 is an acceptable sentinel value for this problem because grades on a quiz are normally nonnegative integers from 0 to 100. Thus, an execution of the class-average program might process a stream of inputs such as 95, 96, 75, 74, 89 and –1. The program would compute and print the class average for the grades 95, 96, 75, 74 and 89 (–1 is the sentinel value, so it should not enter into the average calculation).

We approach the class-average program with a technique called top-down, stepwise refinement, a technique that is essential to the development of well-structured algorithms. 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 purpose. As such, the top is, in effect, a complete representation of a program. Unfortunately, the top rarely conveys sufficient detail from which to write the JavaScript algorithm. Therefore we must begin a refinement process. First, we divide the top into a series of smaller tasks and list them in the order in which they need to be performed, creating the following first refinement:

Initialize variables

Input, sum up and count the quiz grades

Calculate and print the class average

Here, only the sequence structure is used; the steps listed are to be executed in order, one after the other.

To proceed to the next level of refinement (the second refinement), we commit to specific variables. We need a running total of the numbers, a count of how many numbers have been processed, a variable to receive the string representation of each grade as it is input, a variable to store the value of the grade after it is converted to an integer and a vari-able to hold the calculated average. The pseudocode statement

Initialize variables

may be refined as follows:

Initialize total to zero

Note that only the variables total and gradeCounter are initialized before they are used; the variables average, grade and gradeValue (for the calculated average, the user input and the integer representation of the grade, respectively) need not be initialized, because their val-ues are determined as they are calculated or input.

The pseudocode statement

Input, sum up and count the quiz grades

requires a repetition structure (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 will enter legitimate grades, one at a time. After entering the last le-gitimate grade, the user will enter the sentinel value. The program will test for the sentinel value after the user enters each grade and will terminate the loop when the sentinel value is encountered. The second refinement of the preceding pseudocode statement is then

Input the first grade (possibly the sentinel)

While the user has not as yet entered the sentinel

Input the next grade (possibly the sentinel)

Note that in pseudocode, we do not use braces around the pseudocode that forms the body of the While structure. We simply indent the pseudocode under the While, to show that it belongs to the body of the While. Remember, pseudocode is only an informal program-development aid.

The pseudocode statement

Calculate and print the class average

may 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

Note that we are testing for the possibility of division by zero—a logic error that, if unde-tected, would cause the program to produce invalid output. The complete second refine-ment of the pseudocode algorithm for the class-average problem is shown in Fig. 7.8.

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

Initialize total to zero

Input the first grade (possibly the sentinel)

While the user has not as yet entered the sentinel

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

Print the average

Else

Fig. 7.8 | Sentinel-controlled repetition to solve the class-average problem.

Figure 7.9 shows the JavaScript program and a sample execution. Although each grade is an integer, the averaging calculation is likely to produce a number with a decimal point (a real number).

In this example, we see that control structures may be stacked on top of one another (in sequence) just as a child stacks building blocks. The while statement (lines 31–45) is followed immediately by an ifelse statement (lines 48–57) in sequence. Much of the code in this program is identical to the code in Fig. 7.7, so we concentrate in this example on the new features.

Line 21 initializes gradeCounter to 0, because no grades have been entered yet. Remember that the program uses sentinel-controlled repetition. To keep an accurate record of the number of grades entered, the script increments gradeCounter only after processing a valid grade value.

<?xml version = "1.0" encoding = "utf-8"?>

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"

"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">

<!-- Fig. 7.9: average2.html -->

<!-- Sentinel-controlled repetition to calculate a class average. -->

<html xmlns = "http://www.w3.org/1999/xhtml">

<title>Class Average Program: Sentinel-controlled Repetition</title>

<script type = "text/javascript">

<!—

var total; // sum of grades

var average; // average of all grades

// Initialization phase

total = 0; // clear total

gradeCounter = 0; // prepare to loop

// Processing phase

"Enter Integer Grade, -1 to Quit:", "0" );

// convert grade from a string to an integer

while ( gradeValue != -1 )

{

"Enter Integer Grade, -1 to Quit:", "0" );

// convert grade from a string to an integer

} // end while

// Termination phase

if ( gradeCounter != 0 )

{

// display average of exam grades

document.writeln(

"<h1>Class average is " + average + "</h1>" );

} // end if

else

document.writeln( "<p>No grades were entered</p>" );

// -->

</script>

<body>

<p>Click Refresh (or Reload) to run the script again</p>

</body>

</html> Fig. 7.9 | Sentinel-controlled repetition to calculate a class average.

Note the difference in program logic for sentinel-controlled repetition as compared with the counter-controlled repetition in Fig. 7.7. In counter-controlled repetition, we read a value from the user during each iteration of the while statement’s body for the spec-ified number of iterations. In sentinel-controlled repetition, we read one value (lines 25– 26) and convert it to an integer (line 29) before the program reaches the while statement. The script uses this value to determine whether the program’s flow of control should enter the body of the while statement. If the while statement’s condition is false (i.e., the user typed the sentinel as the first grade), the script ignores the body of the while statement (i.e., no grades were entered). If the condition is true, the body begins execution and pro-cesses the value entered by the user (i.e., adds the value to the total in line 34). After pro-cessing the value, the script increments gradeCounter by 1 (line 37), inputs the next grade from the user (lines 40–41) and converts the grade to an integer (line 44), before the end of the while statement’s body. When the script reaches the closing right brace (}) of the body in line 45, execution continues with the next test of the condition of the while state-ment (line 31), using the new value just entered by the user to determine whether the while statement’s body should execute again. Note that the next value always is input from the user immediately before the script evaluates the condition of the while statement. This order allows us to determine whether the value just entered by the user is the sentinel value before processing it (i.e., adding it to the total). If the value entered is the sentinel value, the while statement terminates and the script does not add the value to the total.

Note the block in the while loop in Fig. 7.9 (lines 32–45). Without the braces, the last three statements in the body of the loop would fall outside of the loop, causing the computer to interpret the code incorrectly, as follows:

while  ( gradeValue != -1 )

"Enter Integer Grade, -1 to Quit:", "0" );

This interpretation would cause an infinite loop in the program if the user does not input the sentinel -1 as the first input value in lines 25–26 (i.e., before the while statement).

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Related Topics