GATE CSE 2015 Set 1 | Question: 33

Question

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\}$

Comments

https://gateoverflow.in/118381/gate2017-2-37

---

“ ^ “ is EXOR operator in C language.

take y =2 x= 11 and simply you get option B as answer  

---

Concept in Loop Invariant Problems:

Just take arbitrary values of variables, here x and y as q is already given (0) and perform operations in while loop.

Satisfy the options with the updated values of variables.

 

Answer 1

r is remainder, y is the one dividing x and q is the result.

So, look for this : x = qy + r

P.S: Not standard method.

Answer 2

1. Loop will terminate when r<y

2. Every iteration updates r as r-y​. So the loop iterates r/y times. 'r=x' is given. So we get x/y i.e x get divided by y. 

Hence, x=qy+r would be the second condition.

So, answer would by option B

Answer 3

the pseudo code divides $x$ with $y$ leaving remainder $r$ upto the point when remainder i.e $r<y$

as

$Dividend= Divisor*Quotient +Remainder$ and $remainder < divisor$

x=qy+r and r<y

option B