Java Reference

In-Depth Information

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

Search WWH ::

Custom Search