The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+39 votes
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\}$
in Programming by Boss (29.7k points)
edited by | 3.4k views
0

6 Answers

+45 votes
Best answer

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

@srestha 

@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.

+9 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
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?
+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

by Loyal (7.1k points)
+1

@rishu_darkshadow

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. 

+2 votes
answer is b
by Active (1.4k points)
+2 votes

we can solve by taking some values and after check out with options.

by (249 points)
0 votes
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)
Answer:

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,309 questions
55,747 answers
192,248 comments
90,537 users