The Gateway to Computer Science Excellence

+43 votes

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

- $\{ r = qx + y \wedge r < y\}$
- $\{ x = qy + r \wedge r < y\}$
- $\{ y = qx + r \wedge 0 < r < y\}$
- $\{ q + 1 < r - y \wedge y > 0\}$

+52 votes

Best answer

+15

Sir, can you please correct my logic if I'm wrong?

Option C) and D) are eliminated because after the loop r < y

Initial values assumed: x = 3, y = 1

After loop terminates: x = 3, y = 1, r = 0, q = 3

Option A)

r = (3*3 + 1) ^ True

= 10 ^ True

= 10

But r = 0 after loop terminates, so this option is eliminated

Option B)

x = (3*1 + 0) ^ True

= 3 ^ True

= 3

This condition is satisfied

So option B) is the answer

Option C) and D) are eliminated because after the loop r < y

Initial values assumed: x = 3, y = 1

After loop terminates: x = 3, y = 1, r = 0, q = 3

Option A)

r = (3*3 + 1) ^ True

= 10 ^ True

= 10

But r = 0 after loop terminates, so this option is eliminated

Option B)

x = (3*1 + 0) ^ True

= 3 ^ True

= 3

This condition is satisfied

So option B) is the answer

+1

@rjun Suresh.. Can u please elaborate more.. How you calculate that loop will be executed x/y times and values of q and r

+10 votes

post condition :-

the loop terminates when ( r<y ) so one condition { r<y }

( q=q+1 ) q is increasing every time by 1 so q is simply counting loop count.

so r after execution

r = r - q y

(r=x) so

r = x - q y

x = r + q y

so option B

x = r + qy ^ r < y

the loop terminates when ( r<y ) so one condition { r<y }

( q=q+1 ) q is increasing every time by 1 so q is simply counting loop count.

so r after execution

r = r - q y

(r=x) so

r = x - q y

x = r + q y

so option B

x = r + qy ^ r < y

+1

we are doing

r = r - y and q = q+1 each time

q is increasing every time by one so we can take the value of q as a loop count

so

r = r - 1y < loop runs first time > q = 1

r = r - 2y <loop runs for second time > q = 2 like this

........ after q iteration < r = r - qy > and r = x

so < r = x - qy >

r = r - y and q = q+1 each time

q is increasing every time by one so we can take the value of q as a loop count

so

r = r - 1y < loop runs first time > q = 1

r = r - 2y <loop runs for second time > q = 2 like this

........ after q iteration < r = r - qy > and r = x

so < r = x - qy >

+7 votes

Just take an example and try to solve it by using options:

suppose, x=10 and y=5

begin q := 0 // q = 0 r := x // r = x i.e. r = 5 as value of taken as 10 while r ≥ y do // 10 ≥ 5 ;TRUE(first iteration) begin r := r - y // r = 10 - 5 = 5 q := q + 1 // q= 0 + 1 = 1 end while r ≥ y do // 5 ≥ 5 ;TRUE(second iteration) begin r := r - y // r = 5 - 5 = 0 q := q + 1 // q= 1 + 1 = 2 end while r ≥ y do // 0 ≥ 5 ;FALSE(third iteration) end

at the end of while loop

we get value of r = 0 and q = 2

x= 10 and y = 5

Now one by one put these values in given option

and thus, option B satisfied i.e.

**{x=qy+r∧r<y} // x = 2*5 + 0 = 10 and 0 < 5**

52,223 questions

59,817 answers

201,021 comments

118,089 users