1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
/*
COST Verification Competition. vladimir@cost-ic0701.org
Challenge 1: Maximum in an array
Given: A non-empty integer array a.
Verify that the index returned by the method max() given below points to
an element maximal in the array.
*/
/*@ requires len > 0 && \valid_range(a,0,len-1);
@ ensures 0 <= \result < len &&
@ \forall integer i; 0 <= i < len ==> a[i] <= a[\result];
@*/
int max(int *a, int len) {
int x = 0;
int y = len-1;
/*@ loop invariant 0 <= x <= y < len &&
@ \forall integer i;
@ 0 <= i < x || y < i < len ==>
@ a[i] <= \max(a[x],a[y]);
@ loop variant y - x;
@*/
while (x != y) {
if (a[x] <= a[y]) x++;
else y--;
}
return x;
}
/*
Local Variables:
compile-command: "make array_max.why3ml"
End:
*/
|
