Java Reference

In-Depth Information

that
k
≤
n
. For example, if
s
initially contains
2
values, then initially
k+1=n
,

and incrementing
k
and decrementing
n
makes
k>n
.

7.6.3

Off-by-one errors

An
off-by-one error
occurs when a loop iterates once too many or once too few

times. Many people will tell you that off-by-one errors arise from carelessness,

but that is all they say. They do not tell you
how
to develop the loop condition so

that off-by-one errors do not occur.

If you follow the guidelines given in this text, you will rarely make off-by-

one errors. As we have said earlier, to find a suitable condition for the loop, com-

pare the invariant, for example:

Activity

7-5.4

invariant: The
i
smallest circles have been drawn

with the postcondition, for example:

postcondition: The
n
smallest circles have been drawn

and determine a relation that, together with the invariant, implies the postcondi-

tion, for example”

relation:
i=n

The complement of this relation is then the loop condition:

loop condition:
i!=n

Follow this little methodology and you will rarely make off-by-one errors.

7.6.4

The bound function of a loop

We have been rather informal about checking that a loop makes progress toward

termination. We now look in more detail at what it takes to determine this. We

illustrate the technique using this loop:

Activity

7-5.1

//
Draw
n
circles with centers
(x
,
y)
and radii of
4
,
8
,
12
, …

int
i= 0;

// {
invariant:
i
smallest circles were drawn and
0≤i<n }

while
(i != n) {

int
r= 5+5*i; //
radius of circle
i

g.drawOval(x - i
,
y-i
,
2*i
,
2 * i);

i= i + 1;

}

We introduce what we call a
bound function
, in this case:

Bound function:
n-i

This is an integer expression that gives an
upper bound on the number of itera-

Search WWH ::

Custom Search