Arrays - Multimedia Introduction to Programming Using Java - page 275

Programming tip: After you use a schema a few times, you will have digested it and will not
have to look it up anymore. Be sure to always include the loop invariant because
it is important for others to understand how the loop performs its task.

We end up with this algorithm:

// Process the elements of c[h..k-1] in reverse order
// inv. P: h ≤ i ≤ k and c[i..k-1] has been processed
for ( int i= k; i != h; i= i - 1) {
Process c[i - 1]

See lesson
page 8-3 to get
this program.

}
This algorithm has a somewhat awkward loop body in that it processes c[i
-1] and not c[i] . Let us change the algorithm so that the body can process
c[i] . To do this, we need a new invariant for our postcondition:
postcondition: c[h..k-1] has been processed in reverse order
On the first iteration, c[k - 1] is to be processed. So i has to start at k-1 .
Choosing this initialization forces us to use this invariant, replacing h with i+1
instead of i :
inv: P : c[i + 1..k-1] has been processed
To make the range empty, i has to be initialized to k-1 . The invariant and
the postcondition mean the same thing when i=h-1 . The range of i is now
this: h-1≤i<k. Progress toward termination is still done by decrementing i :
// Process c[h..k-1] , in reverse order
// inv: c[i + 1..k-1] has been processed and h - 1 ≤ i< k
for ( int i= k - 1; i != h - 1; i= i - 1) {
Process c[i]

}
Activity 8-3.3 develops an algorithm from this schema for reading in a list
of values and printing them in reverse order.

Activity
8-3.3

8.3.4 Example: using a schema

This section illustrates the use of the loop schema from Sec. 8.3.2. We develop a
function (see Fig. 8.2) that calculates the number of values in array b that are less
than a given value v . For example, for array b={8 , 2 , 3 , 5 , 7} and value v=5 ,
the function returns 2 because two elements of b are less than 5 . Here is a spec-
ification of the function:

Activity
8-3.4

/** = number of elements of b that are less than v */
public static int numberLess( int [] b, int v)
How will this function be used? Given array d={3 , 5 , 2 , 7 , 3} , the statement