3.4k views

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

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

edited | 3.4k views
0

The loop terminates when $r < y$. So, $r < y$ is one post condition.

In each iteration $q$ is incremented by $1$ and $y$ is subtracted from $r$. Initial value of $r$ is $x$. So, loop iterates $x/y$ times and $q$ will be equal to $x/y$ and $r = x\%y \Rightarrow x = qy + r;$

So, (B) choice.

by Veteran (420k points)
edited by
+14
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
+2
just taking example, we can eleminate options
0

@HvnCool  nice 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
+2
repeated subtractions is equal to dividing
0

@HvnCool How's this happening?

is True is taken as 1?

3 ^ True = 3

0
thank you for good explanation
0

can you pls tell me which operator  '^' is ?Ty in advance

0
Thats the symbolic representation of AND.
0

@Arjun Sir ^ represents Ex-or operator ?

0
No that has to be AND but anyhow I don't think there is as such hard and fast rule, as people commonly write according to the convenience.

Only in standard things you will find the right way.
0
^ is EXOR operator in C language. You have to see the context.
+1

@Arjun sir      @jeetsir.....ty for ur valuable comment.

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
by (483 points)
0
How can u say "r = r - q 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 >
0
u can't say loop runs for q times!
0
@flash12

in the given code , each time the condition in while is satisfied , we increment q. we can say that for n iteration of while loop , q get incremented by n. So  we can also say that the while loop has iterated q times (since q is equal to n).

hence we can write

r=x-qy or x=r+qy
0
^ is a bitwise operator "xor" and how can 8 = 8 ^ True?

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

by Loyal (7.1k points)
+1

Good explanation

In this type of question, i always solve to assume the value, because I'm not comfortable to solve the question in the variable.

by Active (1.4k points)

we can solve by taking some values and after check out with options. by (249 points)
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.
by Junior (931 points)