Section 2.3 More on Proof of Correctness
139
14. Concerning the question posed in Exercise 13:
a. Use the Euclidean algorithm to find the number of packages.
b. How many bottles of shampoo are in each package?
c. How many bars of soap are in each package?
In Exercises 15–21, prove that the program segment is correct by finding and proving the appropriate loop invariant Q and evaluating Q at loop termination.
15. Function to return the value x ∗ y
n
for n ≥ 0.
Computation (integer x; integer y; nonnegative integer n)
Local variables:
integers i, j
i = 0
j = x
while i ≠n do
j = j ∗ y
i = i + 1
end while
//j now has the value x ∗ y
n
return j
end function Computation
16. Function to return the value x – y for x, y ≥ 0.
Difference (nonnegative integer x; nonnegative integer y)
Local variables:
integers i, j
i = 0
j = x
while i ≠ y do
j = j – 1
i = i + 1
end while
//j now has the value x – y
return j
end function Difference
17. Function to return the value (x + 1)
2
for x ≥ 1.
IncrementSquare (positive integer x)
Local variables:
integers i, j
i = 1
j = 4
while i ∙ x do
j = j + 2i + 3
i = i + 1
end while
//j now has the value (x + 1)
2
return j
end function IncrementSquare