edited by
3,268 views
23 votes
23 votes

Consider the program where $a, b$ are integers with $b > 0$.

x:=a; y:=b; z:=0;   
while y > 0 do
    if odd (x) then
        z:= z + x;
        y:= y - 1;
    else y:= y % 2;
        x:= 2 * x;
    fi

Invariant of the loop is a condition which is true before and after every iteration of the loop. In the above program the loop invariant is given by

              $0\leq y$ and $z + x * y= a * b$

Which of the following is true of the program?

  1. The program will not terminate for some values of $a, b$.
  2. The program will terminate with $z=2^{b}$
  3. The program will terminate with $z = a * b$.
  4. The program will not terminate for some values of $a, b$ but when it does terminate, the condition $z = a * b$ will hold.
  5. The program will terminate with $z=a^{b}$
edited by

3 Answers

Best answer
14 votes
14 votes

if $x$ is odd then -

  • $z =a*b$ will be the o/p

if $x$ is even then -   

case 1: if $y$ is even then $x =2*x$ and $z=0$ will be o/p 

case 2: $y$ is odd then loop will not terminate .

EDIT - When x and y are even, for some values of x, condition z= ab is not holding.
For example - when $a=4 \  and  \ b = 4,$ after loop terminates, $z= 8 \ and \ ab = 16.$
$8 \neq 16.$
So, A should be the correct answer.  

edited by
8 votes
8 votes

Option D is correct.

Four possible cases arise here:

1. x = EVEN, y = EVEN

2. x = ODD, y = ODD

3. x = ODD, y = EVEN

4. x = EVEN, y = ODD

Case 1:

x is even, so else part will be executed.

x = 2x, y = 0, z = 0 (z = x*y = a*b)

Case 2:

x is odd, so if part is executed.

After 1st iteration --> x = no change, y reduces by 1, z increases by 1.x.

After 2nd iteration --> x = no change, y = reduces by 2 from the original value, z increase by 2.x (value of x used before the loop).

Here x doesn't change, so the loop will never execute the else part of the code.

The loop will stop only when y becomes 0. As you can see y decreases by 1 every iteration, so final values will be

x = no change, y becomes 0, z = x added y no. of times (i.e z = x*y = a*b).

Case 3:

Same as case 2 where x is odd, so only if part of the code will be executed for every iteration.

The loop will stop when y becomes 0, so the final values will be

x = no change, y becomes 0, z = x added y no. of times (i.e z = x*y =  a*b).

Case 4:

x is even, so for the first iteration, else part will be executed which leads to

x = 2x, y = 1 (odd % 2 = 1), z = 0.

The loop will never end because y > 0 throughout the loop at every iteration.

So for some values of a & b, the loop will never terminate, but if it terminates then z = a*b will hold.

0 votes
0 votes
Option D should be right coz for X= even and Y=odd ,the program doesn't terminate

, For X=Y=even when it terminate the value of Z = a * b.
Answer:

Related questions

12 votes
12 votes
2 answers
3