Java, Java, Java

 

 

 

 

 

Algorithm design: what kind of loop?

 

 

 

 

 

 

 

Algorithm design

Suppose you want to compute the average of your exam grades in a course. Grades, represented as real numbers, will be input from the key- board using our KeyboardReader class. To signify the end of the list, we will use a sentinel value—9999 or 1 or some other value that won’t be confused with a legitimate grade. Because we do not know exactly how many grades will be entered, we will use a noncounting loop in this algorithm. Because there could be no grades to average, we will use a while structure so it is possible to skip the loop entirely in the case that there are no grades to average.

The algorithm should add each grade to a running total, keeping track of the number of grades entered. Thus, this algorithm requires two vari- ables: one to keep track of the running total and the other to keep track of the count. Both should be initialized to 0. After the last grade has been entered, the total should be divided by the count to give the average. In pseudocode, the algorithm for this problem is as follows:

,,

 

 

 

 

 

 

 

 

 

 

Priming read

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Initialization step

J

Note that in this problem our loop variable, grade, is read before the loop test is made. This is known as a priming read. It is necessary in this case, because the loop test depends on the value that is read. Within the loop’s body, the updater reads the next value for grade. This is a standard convention for coding while structures that involve input, as this prob- lem does. Note also that we must make sure that count is not 0 before we attempt to compute the average because dividing by 0 would cause a divide-by-zero error.

Translating the pseudocode algorithm into Java raises several issues. Suppose we store each grade that is input in a double variable named grade. The loop will terminate when grade equals 9999, so its entry con- dition will be (grade != 9999). Because this condition uses grade, it is crucial that the grade variable be initialized before the bound test is made. This requires a priming read. By reading the first value of grade before the loop entry condition is tested, ensures that the loop will be skipped if the user happens to enter the sentinel (9999) on the very first prompt. In addition to reading the first exam score, we must initialize the variables used for the running total and the counter. Thus, for our initialization step, we get the following code:

 

,,

 

 

 

 

J

Within the body of the loop we must add the grade to the running total and increment the counter. Since these variables are not tested in the loop entry condition, they will not affect the loop control. Our loop updater in this case must read the next grade. Placing the updater statement at

the end of the loop body will ensure that the loop terminates immediatelyUpdater step

after the user enters the sentinel value:

,,

 

 

 

 

 

J

You can see that it is somewhat redundant to repeat the same statements needed to do the initializating and the updating of the grade variable. A

better design would be to encapsulate these into a method and then call Modularity

the method both before and within the loop. The method should take care of prompting the user, reading the input, converting it to double, and returning the input value. The method doesn’t require a parameter:

,,

 

 

 

 

 

J

Note that we have declared this as a private method. It will be used to help us perform our task but won’t be available to other objects. Such private methods are frequently called helper methods.

This is a much more modular design. In addition to cutting down on redundancy in our code, it makes the program easier to maintain. For example, there is only one statement to change if we decide to change the

 

prompt message. It also makes the program easier to debug. Input errors are now localized to the promptAndRead() method.

 

 

 

 

 

 

 

Another advantage of encapsulating the input task in a separate method is that it simplifies the task of calculating the average. This task should also be organized into a separate method:

,,

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Method decomposition

J

Note that we have declared this as a public method. This will be the method you call to calculate your course average.

Because we have decomposed the problem into its subtasks, each sub- task is short and simple, making it easier to read and understand. As we saw in the checkerboard example, the use of small, clearly-focused methods is a desireable aspect of designing a program.

The complete Average.java application is shown in Figure 6.10. Its overall design is similar to application programs we designed in previous chapters. The only instance variable it uses is the KeyboardReader vari- able. The other variables are declared locally, within the methods. In this case, declaring them locally makes the algorithms easier to read.

One final point about this program is to note the care taken in the design of the user interface to explain the program to the user, to prompt the user

 

,,

import j ava . io . ;

public c l a s s Average// C o n s o l e I /O

private KeyboardReader reader = new KeyboardReader ( ) ;

 

private double promptAndRead ( )

reader . prompt ( ” Input a grade ( e . g . , 8 5 . 3 ) ” +

” or 9999 to i n d i c a t e the end of the l i s t >> ” ) ;

double grade = reader . getKeyboardDouble ( ) ;

System . out . p r i n t l n ( ”You input ” + grade + ” n” ) ; // C o n f i r m i n p u t

return grade ;

}p ublic double inputAndAverageGrades ( )

double running Total = 0 ;

in t count = 0 ;

double grade = promptAndRead ( ) ;// I n i t i a l i z e : p r i m i n g i n p u t

while ( grade ! = 9999 )// L o o p t e s t : s e n t i n e l

running Total += grade ; count ++;

grade = promptAndRead ( ) ;// U p d a t e : g e t n e x t g r a d e

} // w h i l e

i f ( count > 0 )// G u a r d a g a i n s t d i v i d e −by − z e r o

return running Total / count ;// R e t u r n t h e a v e r a g e

e ls e

return 0 ;// S p e c i a l ( e r r o r ) r e t u r n v a l u e

}p ublic s t a t i c void main ( S t r i n g argv [ ] )

System . out . p r i n t l n ( ” This program c a l c u l a t e s average grade . ” ) ; Average avg = new Average ( ) ;

double average = avg . inputAndAverageGrades ( ) ;

i f ( average == 0 )// E r r o r c h e c k

System . out . p r i n t l n ( ”You didn ’ t enter any grades . ” ) ;

e ls e

System . out . p r i n t l n ( ”Your average i s ” + average ) ;

} // m a i n ( )

// A v e r a g e

\J

Figure 6.10: A program to compute average grade using a while struc- ture.

 

 

before a value is input, and to confirm the user’s input after the program has read it.

 

 

 

 

 

 

 

 

 

 

Algorithm design