edited by
3,451 views
12 votes
12 votes

Consider the following program fragment:

var x, y: integer;
x := 1; y := 0;
while y < x do
begin
   x := 2*x;
   y := y+1
end;

For the above fragment , which of the following is a loop invariant ?

  1. $x=y+1$
  2. $x=(y+1)^2$
  3. $x=(y+1)2^y$
  4. $x=2^y$
  5. None of the above, since the loop does not terminate
edited by

2 Answers

Best answer
17 votes
17 votes

loop invariant is any condition which is true for the start of the loop, for every iteration of the loop and for the exit of the loop.

Before 1st iterations values of $(x,y)$ are $(1,0)$

After 1st iteration values of $x$ and $y$ are $(2,1)$

After 2nd iteration values of $x$ and $y$ are $(4,2)$

After 3rd iteration values of $x$ and $y$ are $(8,3)$

$\vdots$

After nth iteration values of $x$ and $y$ are $(2^n,n)$

This loop will not terminate and that means we need not worry about the condition when loop exits $(p\to q$ is TRUE if $p$ is false) So $E$ is false

$D$ is the right option

selected by
0 votes
0 votes

Best way to solve is by Dry run

See the pattern yourself

 

Answer:

Related questions

12 votes
12 votes
3 answers
1
Arjun asked Dec 18, 2018
2,396 views
Given the following pseudocode for function $\text{printx()}$ below, how many times is $x$ printed if we execute $\text{printx(5)}?$void printx(int n) { if(n==0){ printf...