Consider the following pseudo code, where \(x\) and \(y\) are positive…
2015
Consider the following pseudo code, where \(x\) and \(y\) are positive integers.
begin
q := 0
r := x
while r ≥ y do
begin
r := r - y
q := q + 1
end
end
The post condition that needs to be satisfied after the program terminates is
- A.
\(\{ r = qx + y \wedge r < y\}\) - B.
\(\{ x = qy + r \wedge r < y\}\) - C.
\(\{ y = qx + r \wedge 0 < r < y\}\) - D.
\(\{ q + 1 < r - y \wedge y > 0\}\)
Attempted by 173 students.
Show answer & explanation
Correct answer: B
This loop repeatedly subtracts y from r and counts how many times this subtraction is done.
This is exactly the algorithm for integer division:
x = q⋅y + r with r<y
q = quotient
r = remainder
So the correct post-condition must match this.
Option B is:
{x=qy+r∧r<y}
A video solution is available for this question — log in and enroll to watch it.