NOTE: This transcription was contributed by Martin P.M. van der Burgt, who has devised a process for producing transcripts automatically. Although its markup is incomplete, we believe it serves a useful purpose by virtue of its searchability and its accessibility to text-reading software. It will be replaced by a fully marked-up version when time permits. —HR
An examination exercise, designed by W.H.J.Feijen.
The problem posed to the students that had followed last fall’s course “An Introduction to the Art of Programming” boiled down to the following:
“Given an integer value N (N ≥ 3) and a monotonically increasing sequence of integer values X(0),...,X(N) with X(0) = 0 . For 0 ≤ i < N , the value X(i) represents the clockwise distance along a circle with circumference X(N) of the point P_{i} from the point P_{0} Given also an integer value K (K ≥ 3). Design a program determining whether among the points P_{0} through P_{N-1} , K different points can be selected that are the vertices of a regular K-gon. Because the answer is clearly “no” if X(N) mod K ≠ 0 , X(N) mod K = 0 may be assumed.”
* *
*
(E y: x(N) - d ≤ y < x(N): v(y)) , |
v(y) = (E i: 0 ≤ i < N: X(i) = y) and (0 ≤ y < d or v(y - d)) |
The idea of the algorithm is to keep track of a set
s = { y | b ≤ y < b + d and v(y)} |
yes:= non empty(s) . |
To begin with, b = the smallest element in s ; we propose to maintain that relation as long as s is not empty. Because the size of s is a monotically non-increasing function of b , empty(s) for b < X(N) - d implies empty(s) for b = X(N) - d .
With b defined for non empty(s) as the smallest element of s , a first sketch of our program is
d:= X(N)/ K; s:= empty set; i:= 0; | ||||
do X(i) < d → add X(i) to s ; i:= i + 1 od; | ||||
do non empty(s) cand X(N) > b + d → | ||||
q:= (E i: 0 ≤ i < N: X(i) = b + d); | ||||
if q → replace in s the value b by b + d | ||||
▯ non q → remove from s the value b | ||||
fi | ||||
od | ||||
yes:= non empty(s). |
When we represent the set s by the array ms, the elements of which are the members of s in the order of increasing magnitude, the value b , when defined, equals ms.low .
The assignment to q can be achieved by
q:= (X(i) = b + d) |
begin glocon N, X, K; vircon yes; pricon d; privar ms, i; | ||||
d vir int:= X(N)/ K; ms vir int array := (0); i vir int := 0; | ||||
do X(i) < d → ms:hiext(X(i)); i:= i + l od; | ||||
do ms.dom > 0 cand X(N) > ms.low + d → | ||||
i:= "the smallest solution of X(i) ≥ ms.low + d"; | ||||
if X(i) = ms.low + d → ms:lorem; ms:hiext(X(i)) | ||||
▯ X(i) > ms.low + d → ms:lorem | ||||
fi | ||||
od; | ||||
yes vir bool := ms.dom > 0 | ||||
end |
(A j: 0 ≤ j < i: X(i) < ms.low + d) |
do X(i) < ms.low + d → i:= i + l od . |
8 February 1979
Plataanstraat 5 | prof.dr.Edsger W.Dijkstra |
5671 AL NUENEN | Burroughs Research Fellow |
The Netherlands |
Transcribed by Martin P.M. van der Burgt
Last revision