Computer Sciences > Gate 2017 Set-2 > C code
Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variable x, y, q and r are all unsigned int.

while(r >= y)
{
    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)?
A
( q == r ) && ( r == 0)
B
( x <0 ) && ( r == x ) && ( y > 0 )
C
( q == 0 ) && ( r == x ) && ( y > 0 )
D
( q == 0 ) && ( y > 0 )

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

Consider the following program in C language: #include &lt;stdio.h> main() { &nbsp; &nbsp; int i; &nbsp; &nbsp; int *pi = &i; &nbsp; &nbsp; scanf("%d",...
#16 MCQ
Consider the following two C code segments. Y and X are one and two dimensional arrays of size n and n × n respectively, where 2 ≤ n ≤ 10. Assume that in both c...
#25 MCQ
Consider the following C program segment. #include&lt;stdio.h&gt; int main( ) { &nbsp; &nbsp; char s1[7] = "1234", *p; &nbsp; &nbsp; p = s1 + 2; &nbsp; &nbsp;...
#37 MCQ

Related Topics

C program fragment repeated subtractions division loop termination condition GATE CS 2017 Set-2 program correctness C loop invariant unsigned int variables GATE computer sciences

Unique Visitor Count

Total Unique Visitors

Loading......