GATE CSE 1988 | Question: 6ii

Question

Below figure is the flow-chart corresponding to a program to calculate the $\gcd$ of two integers, $M$ and $N$ respectively, $(M, N >0).$ Use assertions at the cut point $C_1$, $C_2$ and $C_3$ to prove that the flow-chart is correct.

Answer 1

Cond 3 : Evaluating condition where two integers are equal and thus GCD(x,x)=x Thus it is returning X itself.
Cond 2 : We are reducing the Greater integer among 2 by the smallest one which will ultimately reduce it by factor of smaller integer.
Cond1: Provides updated value at other iteration and Original value at 1st iteration./

EX: M=9 N=6
L=9,K=6
Iteration 1 ::Cond 1 :(9! = 6)True --> (K>L)False --> L=3 -->Cond2::Cond1 (Updated value : L=3 K=6) 
Iteration 2 ::Cond1 :(3!=6) True --> (K>L)True --> K=3--> Cond2:: Cond1(Updated Value L=3,K=3)
Iteration 3 ::Cond1 (3!=3) False Cond 3 :: Return K=3 Which is GCD(9,6)=3

Comments

Little correction on last line : 

Iteration 3 :: $Cond1 (3!=6)$  $False$ Cond 3 $::$ Return $K=3$ Which is $GCD(9,6)=3$

here, $Cond1$ $(3!=3)$ $False$ must be there.

---

in last case Cond1 (3!=3) should be there

 

 

 

 

 

---

if anyone wants to know what is Loop invariant then read this         

gfg link

Definition by How to Think About Algorithms, by Jeff Edmonds

A loop invariant  (stackoverflow link)is an assertion that is placed at the top of a loop and that must hold true every time the computation returns to the top of the loop.