question archive Verify {P} S {Q} where S is the following subprogram which searches an array A for the value of a variable x: k := 1; while (k ≤ n ∧ A(k) ≠ x) do k:=k+1 end while The precondition P is (n ∈ Z ∧ 0 ≤ n) where Z is the set of integers and where n is intended to indicate the number of entries in the linear array A
Verify {P} S {Q} where S is the following subprogram which searches an array A for the value of a variable x: k := 1; while (k ≤ n ∧ A(k) ≠ x) do k:=k+1 end while The precondition P is (n ∈ Z ∧ 0 ≤ n) where Z is the set of integers and where n is intended to indicate the number of entries in the linear array A
Subject:Computer SciencePrice: Bought3
Verify {P} S {Q} where S is the following subprogram which searches an array A for the value of a variable x:
k := 1; while (k ≤ n ∧ A(k) ≠ x) do k:=k+1 end while
The precondition P is (n ∈ Z ∧ 0 ≤ n) where Z is the set of integers and where n is intended to indicate the number of entries in the linear array A.
The post condition Q is:
n ∈ Z∧ k ∈ Z
and 1 ≤ k ≤ n+1 (this gives the range of k)
and ????=1A(i)
????−1 ≠ x (so all entries before the k-th ≠ x)
and (k ≤ n and A(k) = x (i.e. either A(k) = x)
or k = n+1 (or no entry in A equals x).
In addition, the programmer has specified the following loop invariant:
n ∈ Z and k ∈ Z and 1 ≤ k ≤ n+1 (k must lie in its range)
and i = 1k−1 A(i) ≠ x (so we haven't previously found x)
