{
r = r - y;
q = q + 1;
}
Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y*q + r)?
Correct : C
Given:
Variables x, y, q, and r are of type unsigned int.
Code fragment:
while(r >= y)
{
r = r - y;
q = q + 1;
}
To find:
The initial condition on the variables before the loop starts to ensure termination with x == (y × q + r).
Solution:
Let me trace the values inside the loop first.
In each iteration of the loop, r decreases by y and q increases by 1.
Let q0 and r0 be the values before entering the loop.
After k iterations, the values become:
q = q0 + k
r = r0 - k × y
Now let me evaluate the expression y × q + r:
y × q + r = y × (q0 + k) + (r0 - k × y)
Multiplying and opening the brackets gives:
y × q + r = y × q0 + k × y + r0 - k × y = y × q0 + r0
So the quantity (y × q + r) is a loop invariant, which always stays equal to the initial value (y × q0 + r0).
We want the final state to satisfy:
x == y × q + r
Therefore, the initial values must satisfy:
x = y × q0 + r0
If we set q0 = 0, then we immediately get:
r0 = x
Now let me check loop termination.
If y = 0, r >= 0 will always be true since r is unsigned int, and r - 0 stays unchanged, so the loop will never terminate.
Thus, to ensure termination, we must have:
y > 0
Combining these conditions, before execution we must have:
( q == 0 ) && ( r == x ) && ( y > 0 )
Answer:
(C) ( q == 0 ) && ( r == x ) && ( y > 0 )
Similar Questions
Total Unique Visitors